Sudoku Solver的代码解释
我对以下代码片断有疑问：它是一个数独解算器，通过填充空单元格来解决数独难题。 我无法真正理解求解器方法背后的逻辑。 为什么在尝试k = 1-9后返回false，并且在遍历所有单元格之后返回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;
}
}
每次递归调用都要照顾第一个'。' 还有待处理。 这将暂时用一个数字代替。 如果更改成功（不会使板失效），请执行递归操作（将尝试下一个'。'）。 如果这将无法撤消在本地完成的更改并返回false，因为在此搜索分支上尝试的任何数字都是无效的。 这意味着强制呼叫者（直到根）尝试下一个选择。
这是一个简单的蛮力解决方案。 它只是在每个开放空间尝试每个数字。 如果棋盘在填充给定空格后用一个数字“有效”（遵循游戏规则），则递归调用同一个求解器函数，填充另一个空白点并测试棋盘是否仍然有效上。
这是一个非常低效的求解器，但易于编码。
此代码检查Sudoku。如果它是正确的，那么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;
}
}
链接地址: http://www.djcxy.com/p/96159.html