Syed Sharuk Chowdhury - 1 year ago 93
C++ Question

Empty Sudoku Filler C++

I'm working on a program that fills in an empty 9x9 array with the proper values for a sudoku board. My validation method works as I've tested it out in a simple iterative backtracking approach.
My current approach is to randomly choose a row and a column and place an appropriate value, I am also implementing backtracking through the use of recursion. Here is my solver function:

``````void solve (int board[9][9]) {

static int counter = 0;
int val = 0;
int row = 0;
int col = 0;

if (counter == 81) {
print (board, counter);
exit(1);
}

while (1) {
row = rand() % 9;
col = rand() % 9;
if (board[row][col] == 0)
break;
}

++counter;
for (int i = 1; i < 10; i++) {
val = i;
if (ok (board, row, col, val)) {
board[row][col] = val;
solve (board);
}
}
--counter;
}
``````

Now the issue I am having is that I never reach 81, my function terminates before that, I am assuming the stack gets empty and returns to main. Can you help me understand what mistake I am making? Thank you.

When you try to fill in a Sudoku grid with appropriate values, you eventually end up in deadlocks : situations where the cell you are trying to find a value for cannot be filled in without breaking Sudoku rules. As a simple example, consider a grid where the first row is `[x, 2, 3, 4, 5, 6, 7, 8, 9]` and the first column is `[x, 1, 8, 2, 3, 4, 5, 6, 7]`. x cannot be filled in, but all of the other values follow the rules.
In your case, when a deadlock happens, the `ok` condition isn't fulfilled by any of the values from 1 to 9 and the execution goes back one layer of recursion, to the previous cell, where a value has already been chosen. There, the function tries the next possible value.
In the case of a deadlock on a cell that has had a value (that is, a multiple-level deadlock), the execution goes back one layer of recursion again, but the value is still there. That causes subsequent `ok` conditions to fail when they should succeed, because of these "ghost" values. The problem doesn't occur for a simple deadlock because the value stays 0.
After the `for` loop, you need to set the value of `board[row][col]` back to 0.