Sudoku拼图求解器Java实施检查

Question

我正在尝试使用Java实现Sudoku拼图求解器，但是下面的代码在第二种情况下失败(它应该返回false(。从打印的输出来看，即使在求解整个网格之前，代码也会退出。我想念什么？

有人可以帮助您快速检查一下，并暗示您看到问题。

问题：编写函数sudokusolve，该功能可以检查给定的Sudoku板(即9x9 Sudoku拼图(。如果是这样，该函数将返回true。否则(即没有针对给定的Sudoku董事会的有效解决方案(，返回false。

代码：

public class Sudoku {
    static boolean sudokuSolve(char[][] board) {
        int row = -1, col = -1;
        List<Integer> candidates = null; // store smallest possible candidates
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') {
                    List<Integer> newCandidates = getCandidates(board, r, c);
                    if (candidates == null || newCandidates.size() < candidates.size()) {
                        candidates = newCandidates;
                        row = r;
                        col = c;
                    }
                }
            }
        }
        if (candidates == null || candidates.isEmpty())
            return true;
        for (Integer val : candidates) {
            board[row][col] = (char) (val.intValue() + '0');
            if (sudokuSolve(board))
                return true;
            else
                board[row][col] = '.';
        }
        printGrid(board);
        return false;
    }
    /**
     * For each empty cell, consider 'newCandidates', the set of possible candidate
     * values that can be placed into that cell.
     * 
     */
    public static List<Integer> getCandidates(char[][] board, int x, int y) {
        // filled row numbers
        boolean[] mask = new boolean[10];
        for (int row = 0; row < 9; row++) {
            char ch = board[row][y];
            if (ch != '.')
                mask[ch - '0'] = true;
        }
        // filled col numbers
        for (int col = 0; col < 9; col++) {
            char ch = board[x][col];
            if (ch != '.')
                mask[ch - '0'] = true;
        }
        // filled subgrid numbers
        // starts at row - row%3, col - col%3
        int subBoardRow = x - (x % 3);
        int subBoardCol = y - (y % 3);
        for (int row = 0; row < 3; row++) {
            for (int col = 0; col < 3; col++) {
                char ch = board[subBoardRow + row][subBoardCol + col];
                if (ch != '.')
                    mask[ch - '0'] = true;
            }
        }
        List<Integer> candidates = new ArrayList<Integer>();
        for (int i = 1; i <= 9; i++) {
            if (!mask[i])
                candidates.add(i);
        }
        return candidates;
    }
      public static void main(String[] args) {
          char[][] board = new char[][] {
              {'.','.','.','7','.','.','3','.','1'},
              {'3','.','.','9','.','.','.','.','.'},
              {'.','4','.','3','1','.','2','.','.'},
              {'.','6','.','4','.','.','5','.','.'},
              {'.','.','.','.','.','.','.','.','.'},
              {'.','.','1','.','.','8','.','4','.'},
              {'.','.','6','.','2','1','.','5','.'},
              {'.','.','.','.','.','9','.','.','8'},
              {'8','.','5','.','.','4','.','.','.'}};
          System.out.println(sudokuSolve(board));
          printGrid(board);
          System.out.println("***************************************");
          char[][] board2 = new char[][] {
              {'.','8','9','.','4','.','6','.','5'},
              {'.','7','.','.','.','8','.','4','1'},
              {'5','6','.','9','.','.','.','.','8'},
              {'.','.','.','7','.','5','.','9','.'},
              {'.','9','.','4','.','1','.','5','.'},
              {'.','3','.','9','.','6','.','1','.'},
              {'8','.','.','.','.','.','.','.','7'},
              {'.','2','.','8','.','.','.','6','.'},
              {'.','.','6','.','7','.','.','8','.'}};
          System.out.println(sudokuSolve(board2));
          printGrid(board2);
      }
      public static void printGrid(char[][] grid) {
            for (int r = 0; r < grid.length; r++) {
                for (int c = 0; c < grid[0].length; c++) {
                    System.out.print(grid[r][c] + " ");
                }
                System.out.print("n");
            }
        }
}

输出：

true
6 5 8 7 4 2 3 9 1 
3 1 2 9 8 6 4 7 5 
7 4 9 3 1 5 2 8 6 
2 6 3 4 9 7 5 . . 
. . . 1 . . . . . 
. . 1 2 . 8 . 4 . 
. . 6 8 2 1 . 5 . 
. . . 5 . 9 . . 8 
8 . 5 6 . 4 . . . 
***************************************

是真的1 8 9 2 4 3 6 7 52 7 3 5 6 8 9 4 15 6 4 9 1 7 2 3 84 1 2 7 3 5 8 9 66 9 8 4 2 1 7 5 37 3 5 9 8 6 4 1 28 4 1。5 9。2 7。2 7 8。。。6。。。6。7。。8。

Answer 1

您的算法有点奇怪。

您有递归，这似乎没有用。对于板上的每个瓷砖，您都会计算候选人，但将其与候选人一起覆盖另一个瓷砖。也许我错了，但是结果有时是真的。
sudokuSolve无法以这种方式正确工作。

---

update

第二个初始板是错误的。4.列(从开始(中有两个 9 。您的算法无法处理这种情况。

问题是错误的，或者问题是(也((还(为初始董事会实现检查器，或者您制作了错字;(