What is up with my sudoku function?

[sero323]

Okay so this has been driving me crazy. I have been working on a sudoku solver and through one of the topics posted on this site (http://www.cplusplus.com/forum/beginner/48341/) i found a backtracking sudoku solver (and made some modifications to it), only that it overwrites my numbers in the array. The backtacking code is below and i read in those exact numbers from a file and input them in the array. After doing so i print the board and then i call the solvePuzzle() function. And when its done i call the print function again to print the "solution". i have tried to put if(check(x,y,num) && arr[x][y] == 0) , but that puts me in an endless loop. Any ideas? (btw check function checks the row/col/3x3 grid for availability)

/* The following is a sample sudoku puzzle that i want to solve. */
// 0 5 0 0 2 0 0 7 0
// 7 2 0 4 0 3 0 0 0
// 9 0 0 0 5 0 6 2 0
// 0 0 5 0 8 6 0 0 0
// 1 0 0 0 4 0 0 0 8
// 0 0 0 2 3 0 4 0 0
// 0 9 3 0 1 0 0 0 2
// 0 0 0 3 0 2 0 4 6
// 0 8 0 0 0 0 0 1 0

// backtracking function
void Sudoku::solvePuzzle()
{
int x = 0;
int y = 0;
int r = 0;
bool back_flag;

while (r < 81) {
    back_flag = true; 
    x = r/9;
    y = r%9;

    for(int num = arr[x][y]; num < 10 && back_flag; num++) {

        if(check(x,y,num)) {
            arr[x][y] = num;
            back_flag=false;
        }
        else if(num >= 9) {
            arr[x][y] = 0;
        }
    }
    if(back_flag) {
        r--;
    }
    else {
        r++;
    }
}
}

[helios]

You can't backtrack without using recursion or a stack structure to hold state information.
In fact, if you read that post, the poster is saying that the code doesn't work.

[sero323]

Well the function works. The poster's code doesn't work but the person who replied with the correction to the code works perfectly fine. This is my output (but as you can tell the original numbers have been changed)

0 1 2 3 4 5 6 7 8
+---------+---------+---------+
0| 3 6 1 | 9 2 8 | 7 5 4 |
1| 8 5 4 | 1 6 7 | 2 3 9 |
2| 2 7 9 | 4 5 3 | 6 8 1 |
+---------+---------+---------+
3| 4 2 7 | 6 8 1 | 3 9 5 |
4| 5 9 6 | 2 3 4 | 1 7 8 |
5| 1 3 8 | 7 9 5 | 4 2 6 |
+---------+---------+---------+
6| 6 1 2 | 8 7 9 | 5 4 3 |
7| 9 4 5 | 3 1 2 | 8 6 7 |
8| 7 8 3 | 5 4 6 | 9 1 2 |
+---------+---------+---------+

[helios]

I just tested it and I killed it after it ran for about two minutes (my computer can solve a worst case Sudoku puzzle in under a minute thirty seconds). I see no way it could work, since it has no way to tell user input from solution data when it overwrites previous incorrect results when backtracking. This leads me to believe that the code merely counts up with a decimal number of 81 digits, hence why it was taking so long.

Again, backtracking requires recursion or some form of a stack. A single flag doesn't hold enough state to solve this problem with backtracking.

EDIT: Compare with my solution: http://www.cplusplus.com/forum/lounge/29126/#msg157845

EDIT 2: Ah, I missed this tiny little comment:
//do smth to check if the value is user-inputted
That's where the stack is.

[sero323]

Ok i looked at the link you posted and i am using the implementation in there. I just have one question i know you declare sudoku matrix = { numbers of sudoku }; but i was wondering is there a way i can use the following to input the numbers in matrix?

    sudoku matrix;
    ifstream fin("sudata.dat");
    
    if (!fin) {
        cout << "Opening File Failed!" << endl;
    }
    else {
        for (int r = 0; r < SIZE*2; r++) {
            for (int c = 0; c < SIZE; c++) {
                fin >> matrix[r][c];
            }
        }
    }

[helios]

Yes. sudoku is merely a typedef for a SIZE by SIZE matrix.

[sero323]

I just changed typedef to int and it worked. char didn't work property, because it was converting int to chars or something.