Code explanation of Sudoku Solver
I have question about the following code snippet: It is a sudoku solver which solves a Sudoku puzzle by filling the empty cells. I can not really get the logic behind the solver method. Why does it return false after trying k=1-9 and return true after looping over all cells. What I thought is we recursively get into solver() method and once the sudoku is done, it will return true back as invoking order and finally the first invoked solver() will return true. I think I must omit some scenarios that above two "return" happen. Could someone explain to me why should those "return" exist?
public class Solution {
public static void main(String[] args) {
Solution s = new Solution();
char[][] board = {{'.', '2', '6', '5', '.', '.', '.', '9', '.'},
{'5', '.', '.', '.', '7', '9', '.', '.', '4'},
{'3', '.', '.', '.', '1', '.', '.', '.', '.'},
{'6', '.', '.', '.', '.', '.', '8', '.', '7'},
{'.', '7', '5', '.', '2', '.', '.', '1', '.'},
{'.', '1', '.', '.', '.', '.', '4', '.', '.'},
{'.', '.', '.', '3', '.', '8', '9', '.', '2'},
{'7', '.', '.', '.', '6', '.', '.', '4', '.'},
{'.', '3', '.', '2', '.', '.', '1', '.', '.'}};
s.solver(board);
}
public boolean solver(char[][] board) {
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < board[0].length; c++) {
if (board[r][c] == '.') {
for (int k = 1; k <= 9; k++) {
board[r][c] = (char) ('0' + k);
if (isValid(board, r, c) && solver(board)) {
return true;
} else {
board[r][c] = '.';
}
}
return false;
}
}
}
return true;
}
public boolean isValid(char[][] board, int r, int c) {
//check row
boolean[] row = new boolean[9];
for (int i = 0; i < 9; i++) {
if (board[r][i] >= '1' && board[r][i] <= '9') {
if (row[board[r][i] - '1'] == false) {
row[board[r][i] - '1'] = true;
} else {
return false;
}
}
}
//check column
boolean[] col = new boolean[9];
for (int i = 0; i < 9; i++) {
if (board[i][c] >= '1' && board[i][c] <= '9') {
if (col[board[i][c] - '1'] == false) {
col[board[i][c] - '1'] = true;
} else {
return false;
}
}
}
//check the 3*3 grid
boolean[] grid = new boolean[9];
for (int i = (r / 3) * 3; i < (r / 3) * 3 + 3; i++) {
for (int j = (c / 3) * 3; j < (c / 3) * 3 + 3; j++) {
if (board[i][j] >= '1' && board[i][j] <= '9') {
if (grid[board[i][j] - '1'] == false) {
grid[board[i][j] - '1'] = true;
} else {
return false;
}
}
}
}
return true;
}
}
Each recursive call take care of the first '.' still to be handled. That will be replaced tentatively with a digit. If the change is successful (does not invalidate the board) go recurse (will try next '.'). If that will fail undo the change done locally and return false, because any digit tried on this search branch is invalid. This means to force the caller (up to root) to try the next choice.
This is a simple brute force solver. It just tries every number in every open space. If the board is 'valid' (follows the rules of the game) after filling in a given space with a number, then it recursively calls the same solver function which fill in another blank spot and test if that the board is still valid and so on.
It is a highly inefficient solver, but easy to code.
This Code Check the Sudoku.If it is correct then check_sudoku() method return true if it wrong then shows the row and column number which has a duplicate element.
public static void main(String[] args) {
int array[][]={{9,6,3,1,7,4,2,5,8},
{1,7,8,3,2,5,6,4,9},
{2,5,4,6,8,9,7,3,1},
{8,2,1,4,3,7,5,9,6},
{4,9,6,8,5,2,3,1,7},
{7,3,5,9,6,1,8,2,4},
{5,8,9,7,1,3,4,6,2},
{3,1,7,2,4,6,9,8,5},
{6,4,2,5,9,8,1,7,3}};
Sudoku sudoku=new Sudoku();
if(sudoku.check_sudoku(array))
{
System.out.println("You won the game :)");
}
}
public class Sudoku {
private int temp1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}, temp2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
private int data1, data2;
public boolean check_sudoku(int array[][]) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
data1 = array[i][j];
data2 = array[j][i];
if (data1 >= 10 || data2 >=10 || data1 <= 0 || data2 <= 0) {
System.out.println("Invalid Solution because value must be in between 1 to 9");
return false;
} else if (temp1[data1 - 1] == 0 || temp2[data2 - 1] == 0) {
System.out.println("Invalid Solution please check " + (i + 1) + " row " + (j + 1) + " column or " + (j + 1) + " row " + (i + 1) + " column");
return false;
} else {
temp1[data1 - 1] = 0;
temp2[data2 - 1] = 0;
}
}
int check1[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int check2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
temp1 = check1;
temp2 = check2;
}
return true;
}
}
链接地址: http://www.djcxy.com/p/96160.html上一篇: 用于解决数独的递归方法
下一篇: Sudoku Solver的代码解释