Syed Sharuk Chowdhury Syed Sharuk Chowdhury - 4 months ago 26
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.

Answer

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.