I have been trying to find out my mistake in the sudoku recovery solver for three days. The problem is related to leetcode Sudoku Solver .
My solver is based on the deduction in the attached picture. The problem is that my board is changing even if the path from root to leaf is invalid.
In other words, after he went through an unacceptable path, the values he tried were fixed on my original board. However, I only update my original board when its children return true (see Part in the helper method: // put the number and generate children).
Basically, for every "." I generate all the possibilities from 1 to 9, create a temporary board that fills the current "." . with one opportunity, then call the assistant of the next "." . with timeline. I know that it’s not good to keep the same boardTemp size for every possible child due to space cost, but now my main task is to solve the problem before optimizing the cost.
All in all, why is my board changing even if all the kids are invalid?
For example, the base on the starting board
.. 9748 ...; 7 ........;. 2.1.9 ...;
.. 7 ... 24.;. 64.1.59 .; 0.98 ... 3 ..;
... 8.3.2.; ........ 6; ... 2759 ..;
I got the final result after starting:
139748652; 745326189; 826159437;
35769.24.;. 64.1.59 .; 0.98 ... 3 ..;
... 8.3.2.; ........ 6; ... 2759 ..;
public void sudokuSolver(char[][] board) { for (int i = 0 ; i < board.length ; i++) { for (int j = 0 ; j < board.length ; j++) { if (board[i][j] == '.') { // find the first '.' as root helper(i, j, board); return; } } } } private boolean helper(int row, int col, char[][] board) { // case 2. check if it has following '.' and store its position boolean hasNext = false; boolean nextSearching = false; int nextRow = row; int nextCol = col; for (int i = 0 ; i < board.length ; i++) { for (int j = 0; j < board.length ; j++) { if (nextSearching && !hasNext && board[i][j] == '.') { hasNext = true; // there is next! nextRow = i; nextCol = j; } if (i == row && j == col) { nextSearching = true; } } } // exit condition: last '.' if (!hasNext) { for (char put = '1' ; put <= '9' ; put ++) { if (isValid(row, col, board, put)) { return true; } } return false; } // put a number and generate children for (char put = '1' ; put <= '9' ; put ++) { if (isValid(row, col, board, put)) { char[][] boardTemp = board; boardTemp[row][col] = put; boolean valid = helper(nextRow, nextCol, boardTemp); if (valid) { // board is supposed to change only when valid is true. board[row][col] = put; return true; } } } return false; } private boolean isValid(int row, int col, char[][] board, char c) { // go through each row, column, and subblock to determine if c is a valid choice based on current board. for (int jCol = 0 ; jCol < 9 ; jCol ++) { if (board[row][jCol] == c) { return false; } } for (int iRow = 0 ; iRow < 9 ; iRow ++) { if (board[iRow][col] == c) { return false; } } for (int i = row/3*3 ; i < row/3*3 + 3 ; i++) { for (int j = col/3*3 ; j < col/3*3 + 3 ; j++) { if (board[i][j] == c) { return false; } } } return true; }
