解数独

发表于 | 更新于 | 分类于

题源：Leetcode-解数独

数独（Sudoku）是一种古老的数学游戏。一个数独的解法需遵循以下规则：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实现分隔的 3x3 宫内只能出现一次。

一个初始的数独题目可以如下：

答案如下：

在我们的函数中，用 char[][] board 来表示数独游戏。其中空白格用 '.' 表示。

解决数独问题，有几种方法。

方法一：回溯法

对于回溯法，大家应该都不太陌生。在著名的算法问题：八皇后 问题中，我们都接触过回溯法。其实就是一种不断尝试的方法，我们对每一个可能的解进行尝试，如果成功即结束，不成功就往回退一步，继续尝试，直至找到解，或者全部尝试完毕，没有解。

在解决数独问题中，我们的回溯法步骤如下：

  1. 遍历所有空白格。对每一个空白格，从 1-9 逐一尝试。如果某一个值合法（不会引起行，列，宫 的冲突），则将其赋值给当前空白格，并继续往下寻找（递归）。
  2. 在这个赋值的前提下，如果最后能够找出解，则成功，返回True。如果不能找到解，则撤回当前的赋值，继续尝试下一个值。如果所有值均尝试过，仍是不能成功，则此数独无解，返回False。
  3. 如果遍历完所有空白格都没有返回，则说明此时board已经全部填充完毕，返回True。

用代码表示如下：（注释详尽，可读性强）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
private boolean backTrack(char[][] board) {
    for (int i = 0;i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            //if the position hasn't been filled, we should try it from 1 to 9.
            if (board[i][j] == '.') {
                for (char c = '1'; c <= '9'; c++) {
                    //if c is valid for the board
                    if (isValid(board, i, j, c)) {
                        board[i][j] = c;  // use c to fill the position
                        if (backTrack(board)) //and continue to fill the board
                            return true;  // we succeed to find the solution.
                        else
                            board[i][j] = '.'; //Ops, we can't find the solution by c in board[i][j], so we give it up, and continue to try the character in board[i][j]
                    }
                }
                return false; //After trying 1 to 9, we still can't find the solution. So we failed in this case. (Will not happen if there is any solution)
            }
        }
    }
    return true; //We traverse the board and it is full. So we return true
}

private boolean isValid(char[][] board, int i, int j, char c) {
    int rowIndex = i / 3 * 3, columeIndex = j / 3 * 3;  // Find two indexes. Used for cube test.
    for (int k = 0; k < 9; k++) {
        if (board[i][k] == c || board[k][j] == c || board[rowIndex + k/3][columeIndex + k%3] == c)
            return false;
    }
    return true;
}

isValid()函数分析

代码中，isValid函数即用来判断：在当前棋盘board中，在（i，j）位置填充字符c是否合法。在以上实现中，我们的做法是：分别在当前（i，j）所在的 行，列，宫 中 判断是否已经存在c，只要某处存在，即返回false。若全都不存在，则返回true。

在这里，每次判断valid的时候，我们都需要进行O(n)复杂度的遍历。

其实我们可以对此做一些改进，利用Hash的思想，将每一个 行，列，宫 用集合的方式（HashSet）表示出来，这样在判断是否存在c的时候，就不需要通过遍历，而可以直接用O(1)的复杂度在HashSet中判断出来。

改进后代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public void solveSudoku(char[][] board) {
    //init three sets
    List<HashSet<Character>> rowSets = new ArrayList<>();
    List<HashSet<Character>> columnSets = new ArrayList<>();
    List<HashSet<Character>> boxSets = new ArrayList<>();
    for (int i = 0; i < 9; i++) {
        rowSets.add(new HashSet<>());
        columnSets.add(new HashSet<>());
        boxSets.add(new HashSet<>());
    }
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != '.') {
                rowSets.get(i).add(board[i][j]);
                columnSets.get(j).add(board[i][j]);
                boxSets.get(i/3*3 + j/3).add(board[i][j]);
            }
        }
    }

    backTrack(board, rowSets, columnSets, boxSets);
}

//method one: backtrack
private boolean backTrack(char[][] board, List<HashSet<Character>> rowSets, List<HashSet<Character>> columnSets, List<HashSet<Character>> boxSets) {
    for (int i = 0;i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            //if the position hasn't been filled, we should try it from 1 to 9.
            if (board[i][j] == '.') {
                for (char c = '1'; c <= '9'; c++) {
                    //if c is valid for the board
                    if (!rowSets.get(i).contains(c) && !columnSets.get(j).contains(c) && !boxSets.get(i/3*3+j/3).contains(c)) {
                        board[i][j] = c;  // use c to fill the position
                        rowSets.get(i).add(c);
                        columnSets.get(j).add(c);
                        boxSets.get(i/3*3+j/3).add(c);
                        if (backTrack(board, rowSets, columnSets, boxSets)) //and continue to fill the board
                            return true;  // we succeed to find the solution.
                        else {
                            board[i][j] = '.'; //Ops, we can't find the solution by c in board[i][j], so we give it up, and continue to try the character in board[i][j]
                            rowSets.get(i).remove(c);
                            columnSets.get(j).remove(c);
                            boxSets.get(i/3*3+j/3).remove(c);
                        }
                    }
                }
                return false; //After trying 1 to 9, we still can't find the solution. So we failed in this case. (Will not happen if there is any solution)
            }
        }
    }
    return true; //We traverse the board and it is full. So we return true
}

时间复杂度分析

在这种方法中，最坏情况下，需要对board中所有的空白格进行1～9的尝试。从排列组合的角度，设空白格数目为m，可以轻易地得出最坏有 9^m 种可能。所以算法的时间复杂度为 O(9^m)，为指数级别…

可以看出，如果数独的规模更加庞大，这种方法的可行性会大大降低，因为指数级的复杂度在增长速度上是十分恐怖的。

所以我们接下来尝试其他的方法，对解数独的过程进行优化。

网格更新传播+回溯法

我们对board中的每一个网格cell，封装一个struct，记录其中目前可以取的值，初始化时可以取1～9所有值。

然后，我们对board里所有的网格进行遍历，每次碰到已填充值的网格，就对其影响的所有网格的可取值进行更新，并且在这一过程中，如果某一个网格的可取值只剩一个，就对其进行赋值，并且进一步更新其他网格可取值…

以此状态，形成了一个动态的更新传播过程。在此次遍历中，能够将所有能够确定的值全部找出并且赋值。至此，80%以上的数独游戏已经解决完毕了。

如果还有不能确定值的网格，我们就只能进行backTrack回溯法了。回溯的过程中，为了减小尝试次数，我们从剩余可取值最少的网格开始尝试。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
public void solveSudoku(char[][] board) {
    Cell[][] cells = new Cell[9][9];
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cells[i][j] = new Cell(i, j);
        }
    }
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != '.') {
                set(cells, i, j, board[i][j]);
            }
        }
    }
    //in most case, the algorithm ends here.
    //Or we can only use backtrack（回溯）now.
    ArrayList<Cell> remains = new ArrayList<Cell>();
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (cells[i][j].value == '.')
                remains.add(cells[i][j]);
        }
    }
    //sort the remains. So we can try the cell that has less possibilities first.
    remains.sort(new Comparator<Cell>() {
        @Override
        public int compare(Cell o1, Cell o2) {
            return o1.remains.size() - o2.remains.size();
        }
    });

    backTrackRemains(cells, remains, 0);
    //transfer cells.value into board
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            board[i][j] = cells[i][j].value;
        }
    }
}

private boolean set(Cell[][] cells, int i, int j, char c) {
    if (cells[i][j].value == c)
        return true;
    else if (cells[i][j].value != '.' || !cells[i][j].remains.contains(c))
        return false;
    int rowIndex = i / 3 * 3, columnIndex = j / 3 * 3;
    cells[i][j].value = c;
    //cells[i][j].remains.clear();
    //propagate constraints
    for (int k = 0; k < 9; k++) {
        //check row
        if (i != k) {
            if (cells[k][j].value == c)
                return false;
            if (cells[k][j].value == '.' && cells[k][j].remains.remove(new Character(c))) {
                if (cells[k][j].remains.size() == 1) {
                    if (!set(cells, k, j, cells[k][j].remains.get(0)))
                        return false;
                }
            }
        }
        //check column
        if (j != k) {
            if (cells[i][k].value == c)
                return false;
            if (cells[i][k].value == '.' && cells[i][k].remains.remove(new Character(c))) {
                if (cells[i][k].remains.size() == 1) {
                    if (!set(cells, i, k, cells[i][k].remains.get(0)))
                        return false;
                }
            }
        }
        //check box
        if (rowIndex + k / 3 != i || columnIndex + k % 3 != j) {
            if (cells[rowIndex + k/3][columnIndex+k%3].value == c)
                return false;
            if (cells[rowIndex + k/3][columnIndex+k%3].value == '.' && cells[rowIndex + k/3][columnIndex+k%3].remains.remove(new Character(c))) {
                if (cells[rowIndex + k / 3][columnIndex + k % 3].remains.size() == 1) {
                    if (!set(cells, rowIndex + k / 3, columnIndex + k % 3, cells[rowIndex + k / 3][columnIndex + k % 3].remains.get(0)))
                        return false;
                }
            }
        }
    }
    return true;
}

private boolean backTrackRemains(Cell[][] cells, ArrayList<Cell> remains, int t) {
    if (t == remains.size())
        return true;
    Cell cell = remains.get(t).copy();
    List<Character> remainChars = cell.remains;
    //Cell[][] tempCells = cells.clone();  //Used to restore cells. FAILURE!
    Cell[][] tempCells = new Cell[9][9]; //Must restore like this.
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++)
            tempCells[i][j] = cells[i][j].copy();   //use copy() to copy the value, not the reference!
    }
    for (char c: remainChars) {
        if (set(cells, cell.i, cell.j, c)) {

            if (backTrackRemains(cells, remains, t+1)) {
                return true;
            }

        }
        // restore cells
        /* Attention:
         * 1. We can't change cells themselves, like cells[i][j] = tempCells[i][j], because we are referring cells in ArrayList<Cell> remains.
         * 2. We can't refer field in tempCells to cells, cause it will change the value in tempCells.
         * So we can only make assignment from tempCells to cells one by one.
         */
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                cells[i][j].value = tempCells[i][j].value;
                //cells[i][j].remains = tempCells[i][j].remains
                cells[i][j].remains = new ArrayList<>();
                cells[i][j].remains.addAll(tempCells[i][j].remains);
            }
        }
    }
    return false;
}

其中尤其值得注意的是java中的 引用。当我们在给对象赋值的时候，其实赋值的是对对象的引用，而不是对象本身。在以上代码中，我们在backTrackRemains()函数中需要保存住当前cells的值，以便后续恢复，所以引入了tempCells。