在Java问题中蛮力数独求解算法
除了解决方法之外，一切似乎都能在算法中正常工作。 当它使用可解数独板执行程序时，它说它不能解决。 我已经尝试了解决方法中所能想到的一切。 我试过调试，并且在测试第一行后失败。 有什么建议么？ 以下是迄今为止的完整代码：
public class SudokuSolver {
public static void initializeGrid(int[][] grid, int[][] puzzle) {
for (int r = 0; r < puzzle.length; r++) {
for (int c = 0; c < puzzle[0].length; c++) {
grid [r][c] = puzzle [r][c];
}
}
}
public static void displayGrid(int[][] grid) {
for (int r = 0; r < grid.length; r++) {
if (r % 3 == 0) {
System.out.println("+---+---+---+");
}
for (int c = 0; c < grid[r].length; c++) {
if (c % 3 == 0) {
System.out.print("|");
}
displayDigits(r, c, grid);
} System.out.print（“|”）; 的System.out.println（）; } System.out.println（“+ --- + --- + --- +”）; }
if（grid [r] [c] == 0）{System.out.print（''）; } else {System.out.print（grid [r] [c]）; }} public static int getEmptyCells（int [] [] grid，int [] [] emptyCells）{int i = 0; int numEmptyCells = 0; for（int r = 0; r <grid.length; r ++）{for（int c = 0; c <grid [r] .length; c ++）{if（grid [r] [c] == 0）{emptyCells [i] [0] = r; emptyCells [i] [1] = c; numEmptyCells ++; 我++; }}} return numEmptyCells; }
private static boolean hasNoDuplicates（int [] digitsList）{for（int j = 0; j <digitsList.length; j ++）{for（int k = j + 1; k <digitsList.length; k ++）{if（digitsList [j ] == digitsList [k] && digitsList [j]！= 0）return false; }}返回true; }
private static boolean checkCurrentRow（int [] [] grid，int currentRow）{
int [] digitsList = new int [grid.length]; for（int c = 0; c <digitsList.length; c ++）{digitsList [c] = grid [currentRow] [c]; } if（hasNoDuplicates（digitsList））{return true; }返回false; }
private static boolean checkCurrentCol（int [] [] grid，int currentCol）{int [] digitsList = new int [grid.length]; for（int i = 0; i <digitsList.length; i ++）{digitsList [i] = grid [i] [currentCol]; } if（hasNoDuplicates（digitsList））{return true; }返回false; }
private static boolean checkCurrentRegion（int [] [] grid，int currentRow，int currentCol）{
int [] digitsList = new int [grid.length]; currentRow =（currentRow / 3）* 3; currentCol =（currentCol / 3）* 3; int i = 0; for（int r = 0; r <3; r ++）{for（int c = 0; c <3; c ++）{digitsList [i] = grid [currentRow + r] [currentCol + c]; 我++; }} if（hasNoDuplicates（digitsList））{return true; }返回false; }
public static boolean isConsistent（int [] [] grid，int currentRow，int currentCol）{if（checkCurrentRow（grid，currentRow）&& checkCurrentCol（grid，currentCol）&& checkCurrentRegion（grid，currentRow，currentCol））{return true; }返回false; }
public static boolean solvePuzzle（int [] [] grid，int [] [] emptyCells，int numEmptyCells）{int i = 0; int j = 0; int currentCellDigit = grid [emptyCells [i] [0]] [emptyCells [i] [1]]; while（j <numEmptyCells）{if（currentCellDigit！= 9）{currentCellDigit ++; grid [emptyCells [i] [0]] [emptyCells [i] [1]] = currentCellDigit; if（isConsistent（grid，emptyCells [i] [0]，emptyCells [i] [1]））{grid [emptyCells [i] [0]] [emptyCells [i] [1]] = currentCellDigit; 我++; J ++; } else {grid [emptyCells [i] [0]] [emptyCells [i] [1]] = currentCellDigit - 1; }} else {currentCellDigit = 0; currentCellDigit = grid [emptyCells [i] [0]] [emptyCells [i] [1]]; 一世 - ; j--; if（j <0）{return false; }}}
返回true;
}
public static void main（String [] args）{
final int SIZE = 9; int [] [] puzzle = {{0,2,9,0,0,3,0,0,5}，{5,0,7,0,0,0,0,9,0}，{6 ，0,0,0,0,9,4,2,0}，{3,0,2,0,0,4,0,0,0}，{0,0,5,0,3,0 ，7,0,0}，{0,0,0,5,0,0,6,0,2}，{0,9,8,4,0,0,0,0,3}，{0 ，3,0,0,0,0,1,0,6}，{2,0,0,3,0,0,9,4,0}};
int [] [] grid = new int [SIZE] [SIZE]; int [] [] emptyCellsList = new int [SIZE * SIZE] [2]; int numEmptyCells = 0;
initializeGrid（grid，puzzle）; numEmptyCells = getEmptyCells（grid，emptyCellsList）; System.out.println（“The puzzle：”）; displayGrid（难题）; 如果（solvePuzzle（grid，emptyCellsList，numEmptyCells））{System.out.println（“has been resolved：”）; displayGrid（网格）; }其他{System.out.println（“无法解决！”）; }}} 你的initializeGrid是错误的。 恕我直言，它应该是：
for (int c = 0; c < puzzle[r].length; c++)
代替
for (int c = 0; c < puzzle[0].length; c++)
编辑：我的答案低于此
它已被正确缩进（第1课）并相应地安排大括号（第2课）。 学习如何逐行理解你正在尝试做什么，以及何时遇到特定的线路或方法调用，寻求帮助（第3课）。 下面的代码将编译，但不会（尚未）解决这个难题。 阅读并替换solvePuzzle中的注释给我（第四课）。 做一些思考和分析，因为这是你的功课;）祝你好运！
public class SudokuSolver {
public static void initializeGrid(int[][] grid, int[][] puzzle) {
for (int r = 0; r < puzzle.length; r++) {
for (int c = 0; c < puzzle[0].length; c++) {
grid [r][c] = puzzle [r][c];
}
}
}
public static void displayDigits(int r, int c, int[][] grid) {
if (grid[r][c] == 0) {
System.out.print('0');
} else {
System.out.print(grid[r][c]);
}
}
public static void displayGrid(int[][] grid) {
for (int r = 0; r < grid.length; r++) {
if (r % 3 == 0) {
System.out.println("+---+---+---+");
}
for (int c = 0; c < grid[r].length; c++) {
if (c % 3 == 0) {
System.out.print("|");
}
displayDigits(r, c, grid);
}
System.out.print("|");
System.out.println();
}
System.out.println("+---+---+---+");
}
public static int getEmptyCells(int[][] grid, int[][] emptyCells) {
int i = 0;
int numEmptyCells = 0;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[r].length; c++) {
if (grid[r][c] == 0) {
emptyCells[i][0] = r;
emptyCells[i][1] = c;
numEmptyCells++;
i++;
}
}
}
return numEmptyCells;
}
private static boolean hasNoDuplicates(int[] digitsList) {
for (int j = 0; j < digitsList.length; j++) {
for (int k = j + 1; k < digitsList.length; k++) {
if (digitsList[j] == digitsList[k] && digitsList[j] != 0)
return false;
}
}
return true;
}
private static boolean checkCurrentRow(int[][] grid, int currentRow) {
int[] digitsList = new int[grid.length];
for (int c = 0; c < digitsList.length; c++) {
digitsList[c] = grid[currentRow][c];
}
if (hasNoDuplicates(digitsList)) {
return true;
}
return false;
}
private static boolean checkCurrentCol(int[][] grid, int currentCol) {
int[] digitsList = new int[grid.length];
for (int i = 0; i < digitsList.length; i++) {
digitsList[i] = grid[i][currentCol];
}
if (hasNoDuplicates(digitsList)) {
return true;
}
return false;
}
private static boolean checkCurrentRegion(int[][] grid, int currentRow, int currentCol) {
int[] digitsList = new int[grid.length];
currentRow = (currentRow / 3) * 3;
currentCol = (currentCol / 3) * 3;
int i = 0;
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
digitsList[i] = grid[currentRow + r][currentCol + c];
i++;
}
}
if (hasNoDuplicates(digitsList)) {
return true;
}
return false;
}
public static boolean isConsistent(int[][] grid, int currentRow, int currentCol) {
boolean checkRow = checkCurrentRow(grid, currentRow);
boolean checkCol = checkCurrentCol(grid, currentCol);
boolean checkReg = checkCurrentRegion(grid, currentRow, currentCol);
System.out.println("r: " + checkRow + " c: " + checkCol + " r: " + checkReg);
if (checkRow && checkCol && checkReg) {
return true;
}
return false;
}
public static boolean solvePuzzle(int[][] grid, int[][] emptyCells, int numEmptyCells) {
int i = 0;
int currentCellDigit = 0;
while (i < numEmptyCells) {
if (currentCellDigit != 9) {
// increment cell value
currentCellDigit++;
// assign to current cell the current cell value
//<var> = currentCellDigit;
System.out.println("Solving---------------------- :" + currentCellDigit + " R: " + emptyCells[i][0] + " C: " + emptyCells[i][1]);
// check if value is valid
if (isConsistent(grid, emptyCells[i][0], emptyCells[i][1])) {
// reset after setting
i++;
currentCellDigit = 0;
} else {
// reset cell to zero instead of decrementing it since we're backtracking!
//grid[emptyCells[i][0]][emptyCells[i][1]] = currentCellDigit - 1;
//<var> = 0;
}
} else {
// reset current cell to 0
//<var> = 0;
// go to previous cell
i--;
// exit if theres no cell to backtrack to
if (i < 0) {
return false;
}
// set previous' cell value as current cell value
//<var> = grid[emptyCells[i][0]][emptyCells[i][1]];
}
}
return true;
}
public static void main(String[] args) {
final int SIZE = 9;
int[][] puzzle = { {0,2,9,0,0,3,0,0,5},
{5,0,7,0,0,0,0,9,0},
{6,0,0,0,0,9,4,2,0},
{3,0,2,0,0,4,0,0,0},
{0,0,5,0,3,0,7,0,0},
{0,0,0,5,0,0,6,0,2},
{0,9,8,4,0,0,0,0,3},
{0,3,0,0,0,0,1,0,6},
{2,0,0,3,0,0,9,4,0}
};
int[][] grid = new int[SIZE][SIZE];
int[][] emptyCellsList = new int[SIZE*SIZE][2];
int numEmptyCells = 0;
initializeGrid(grid, puzzle);
numEmptyCells = getEmptyCells(grid, emptyCellsList);
System.out.println("The puzzle:");
displayGrid(puzzle);
if (solvePuzzle(grid, emptyCellsList, numEmptyCells)) {
System.out.println("has been solved:");
displayGrid(grid);
} else {
System.out.println("cannot be solved!");
}
}
}
PS这将做回溯，如果你已经用正确的代码替换上面的评论。
在solvePuzzle考虑你的代码。 grid和currentCellDigit之间有多个冗余分配。 i和j是多余的，他们有相同的价值。
使用调试器来了解你的代码在做什么。
更好的缩进将使您的代码更具可读性。
public static boolean solvePuzzle(int[][] grid, int[][] emptyCells,
int numEmptyCells) {
int i = 0;
int currentCellNum = 0;
while (i < numEmptyCells) {
currentCellNum = grid[emptyCells[i][0]][emptyCells[i][1]];
if (currentCellNum != 9) {
currentCellNum++;
grid[emptyCells[i][0]][emptyCells[i][1]] = currentCellNum;
if (isConsistent(grid, emptyCells[i][0], emptyCells[i][1])) {
i++;
}
} else {
currentCellNum = 0;
grid[emptyCells[i][0]][emptyCells[i][1]] = currentCellNum;
i--;
if (i < 0) {
return false;
}
}
}
return true;
}