java 数独求解器代码说明
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15182546/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Code explanation of Sudoku Solver
提问by shirley
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?
我对以下代码片段有疑问：这是一个数独求解器，它通过填充空单元格来解决数独难题。我无法真正理解求解器方法背后的逻辑。为什么在尝试 k=1-9 后返回 false 并在遍历所有单元格后返回 true。我认为我们递归地进入solver() 方法，一旦数独完成，它将返回true 作为调用顺序，最后第一个调用的solver() 将返回true。我想我必须省略一些上面两个“返回”发生的场景。有人可以向我解释为什么这些“回报”应该存在？
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;
}
}
采纳答案by CapelliC
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.
每个递归调用都会处理第一个 '.' 仍有待处理。这将暂时替换为一个数字。如果更改成功（不会使板无效），则递归（将尝试下一个“.”）。如果这将失败，则撤消本地所做的更改并返回 false，因为在此搜索分支上尝试的任何数字都是无效的。这意味着强制调用者（直到 root）尝试下一个选择。
回答by Justin Peel
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.
这是一个非常低效的求解器，但易于编码。
回答by Rishabh Rawat
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.
此代码检查数独。如果正确，则 check_sudoku() 方法返回 true 如果错误则显示具有重复元素的行号和列号。
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;
}
}
}
