37. 解数独

  |   0 评论   |   0 浏览

来源力扣(LeetCode)
难度:困难

题目描述
编写一个程序,通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则:

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
    空白格用 '.' 表示。


一个数独。


答案被标成红色。

Note:

  • 给定的数独序列只包含数字 1-9 和字符 '.' 。
  • 你可以假设给定的数独只有唯一解。
  • 给定数独永远是 9x9 形式的。

题解

方法一:回溯算法

 1class Solution {
 2    // 用于计数的数组
 3    private int[][] rowCounts = new int[9][9]; // 行
 4    private int[][] colCounts = new int[9][9]; // 列
 5    private int[][] subCounts = new int[9][9]; // 子数独
 6
 7    public void solveSudoku(char[][] board) {
 8        // 记录数字的数量
 9        for (int row = 0; row < 9; row++) {
10            for (int col = 0; col < 9; col++) {
11                if (board[row][col] != '.') {
12                    int currNum = board[row][col] - '1';
13                    rowCounts[row][currNum] = 1;
14                    colCounts[col][currNum] = 1;
15                    subCounts[(row/3)*3 + col/3][currNum] = 1;
16                }
17            }
18        }
19
20        backtrack(board, 0, 0);
21    }
22
23    private boolean backtrack(char[][] board, int row, int col) {
24        if (row > 8) {
25            return true;
26        }
27
28        if (board[row][col] == '.') {
29            // 将 1~9 分别填入
30            for (char ch = '1'; ch <= '9'; ch++) {
31                int num = ch - '1';
32                // 若该数字在当前行、列和子数独中已经存在,则跳过
33                if (rowCounts[row][num] == 1 || colCounts[col][num] == 1 || subCounts[(row / 3) * 3 + col / 3][num] == 1) {
34                    continue;
35                }
36
37                // 填入数字
38                board[row][col] = ch;
39                rowCounts[row][num] = 1;
40                colCounts[col][num] = 1;
41                subCounts[(row / 3) * 3 + col / 3][num] = 1;
42
43                // 若找到一个解,则返回true
44                if (backtrack(board, row + (col + 1) / 9, (col + 1) % 9)) {
45                    return true;
46                }
47
48                // 若未找到解,则回溯(返回上一步)
49                board[row][col] = '.';
50                rowCounts[row][num] = 0;
51                colCounts[col][num] = 0;
52                subCounts[(row / 3) * 3 + col / 3][num] = 0;
53            }
54        } else {
55            return backtrack(board, row + (col + 1) / 9, (col + 1) % 9);
56        }
57
58        return false;
59    }
60}