Syed Sharuk Chowdhury - 2 months ago 4x

C++ Question

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.

Source (Stackoverflow)

Comments