Java问题中的蛮力数独求解器算法 [英] Brute force sudoku solver algorithm in Java problem
问题描述
除求解方法外，该算法中的所有功能似乎都可以正常工作。当使用可解决的数独板执行程序时，表示无法解决。我已经尝试了所有可以解决的方法。我尝试调试，但在测试第一行后失败。有什么建议么？这是到目前为止的完整代码：
Everything seems to work fine in the algorithm besides the solve method. When it executes the program using a solvable Sudoku board, it says that it cannot be solved. I've tried everything I can think of in the solve method. I've tried debugging and it fails after the first row is tested. Any suggestions? Here is the full code so far:
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（ + --- + --- + --- +）;
}
} System.out.print("|"); System.out.println(); } System.out.println("+---+---+---+"); }
如果（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
emptyCells [i] [0] = r;
emptyCells [i] [1] = c;
numEmptyCells ++;
i ++;
}
}
}
返回numEmptyCells;
}
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++; i++; } } } return numEmptyCells; }
私有静态布尔hasNoDuplicates（int [] digitsList）{
for（int j = 0; j< digitsList.length; j ++ ）{
for（int k = j +1; k
返回false；
}
}
返回true；
}
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; }
私有静态布尔checkCurrentRow（int [] [] grid，int currentRow）{
int [] digitsList = new int [grid.length];
for（int c = 0; c
}
if（hasNoDuplicates（digitsList））{
返回true;
}
返回false；
}
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;
}
私有静态布尔checkCurrentCol（int [] [] grid，int currentCol）{
int [] digitsList = new int [grid。长度];
for（int i = 0; i
}
if（hasNoDuplicates（digitsList））{
返回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; } return false; }
私有静态布尔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））{
返回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];
i++;
}
}
if (hasNoDuplicates(digitsList)) {
return true;
}
return false;
}
公共静态布尔值isConsistent（int [] [] grid，int currentRow，int currentCol）{
if（checkCurrentRow（grid，currentRow ）&& checkCurrentCol（grid，currentCol）
&& checkCurrentRegion（grid，currentRow，currentCol））{
返回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; } return false; }
公共静态布尔solvePuzzle（int [] []网格，int [] [] emptyCells，int numEmptyCells）{
int i = 0;
int j = 0;
int currentCellDigit = grid [emptyCells [i] [0]] [emptyCells [i] [1]];
而（j
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;
i ++;
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;
}
}
}
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; i++; j++; } else { grid[emptyCells[i][0]][emptyCells[i][1]] = currentCellDigit - 1; } } else { currentCellDigit = 0; currentCellDigit = grid[emptyCells[i][0]][emptyCells[i][1]]; i--; j--; if (j < 0) { return false; } } }
返回true；
}
return true;
}
public static void main（String [] args）{
public static void main(String[] args) {
final int SIZE = 9;
int [] []拼图= {{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}
};
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 [] []网格= new int [SIZE] [SIZE];
int [] [] emptyCellsList = new int [SIZE * SIZE] [2];
int numEmptyCells = 0;
int[][] grid = new int[SIZE][SIZE]; int[][] emptyCellsList = new int[SIZE*SIZE][2]; int numEmptyCells = 0;
推荐答案
您的initializeGrid错误。恕我直言，应该是：
Your initializeGrid is wrong. IMHO, it should be:
for (int c = 0; c < puzzle[r].length; c++)
而不是
for (int c = 0; c < puzzle[0].length; c++)
编辑：我在此下方的答案
my answer below this
已正确缩进（第1课），并相应地排列了花括号（第2课）。学习了解您试图逐行执行的操作，以及当您陷入特定的行或方法调用时，寻求帮助（第3课）。下面的代码可以编译，但不能（尚未）解决难题。为我阅读并替换solvePuzzle中的注释（第4课）。做一些思考和分析，因为这是您的家庭作业；）祝您好运！
It's been indented properly (lesson 1) and arranged the curly braces accordingly (lesson 2). Learn to understand what you are trying to do line by line and when you are stuck on a specific line or method call, look for help (lesson 3). The code below will compile but will not (yet) solve the puzzle. Read and replace the comments inside solvePuzzle for me (lesson 4). Do some thinking and analyzing since this is your homework ;) Good luck!
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!");
}
}
}
P.S。如果您使用正确的代码替换了上面的注释，则会进行回溯。
P.S. this will do backtracking if you've replaced the comments above with proper code.
这篇关于Java问题中的蛮力数独求解器算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
