Sudoku 数独 + 矩阵 Index Trick

Valid Sudoku

这题本身不是很难，也有很多写法都可以 AC. 但是不同解法的简洁程度不同，也能体现出对二维矩阵结构理解上的差异。

Sudoku 是一个结构比较特殊的二维矩阵，因为作为一个正方形矩阵，大多数问题只需要考虑“行”“列”与“对角线”(N-Queens)，而 Sudoku 需要还考虑“子矩阵”，也就是说需要另外的 index trick 去简洁高效的处理“遍历子矩阵”的问题。

下面的代码来自 LeetCode 论坛，简洁准确，值得学习~

x = k / 3 + (i / 3) * 3;

y = k % 3 + (i % 3) * 3;

一个二维矩阵可以变成一维向量，通过 i / size 表示“行”，i % size 表示“列”。

把 Sudoku 以“子矩阵”为单位去想的话，是一个新的 3x3 二维矩阵

(i / 3) * 3 可以作为一个“子矩阵”的 offset，代表在 3x3 子矩阵中的“行”，

(i % 3) * 3 代表子矩阵的“列”。

由于最外圈循环为 i，给定 i 之后我们要实现每个 block 的遍历，因此和 i 相关的 index 用于定位 block.

而后再去加上矩阵本身的“行” k / 3 与 “列” k % 3 实现对于每一个原矩阵坐标 (i, k)，得到对应的子矩阵坐标 (x,y) 映射。

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        for(int i = 0; i < 9; i++){
            boolean[] row = new boolean[9];
            boolean[] col = new boolean[9];

            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.'){
                    int num = board[i][j] - '1';
                    if(row[num]) return false;

                    row[num] = true;
                }

                if(board[j][i] != '.'){
                    int num = board[j][i] - '1';
                    if(col[num]) return false;

                    col[num] = true;
                }
            }

            boolean[] cell = new boolean[9];
            for(int k = 0; k < 9; k++){
               int x = k / 3 + (i / 3) * 3;
               int y = k % 3 + (i % 3) * 3;

               if(board[x][y] != '.'){
                   int num = board[x][y] - '1';
                   if(cell[num]) return false;

                   cell[num] = true;
               }
            }
        }

        return true;
    }
}

Sudoku Solver

这个解借鉴的 LeetCode 论坛答案，思路和 N-Queens 很像，不同之处是存的所有 row, col 和 block.

这个答案据作者 自己描述 在老版本LeetCode Java 上没太大区别，然而 C++ 比较明显。

这题因为检查 “isValid” 的次数非常多，要直接开一个 2D array 了，matrix[index][num] 代表“第 index 行/列/子矩阵” 的“数字num”

因此在 block 的 index 上面可以更取巧一些，给定一个原始矩阵的位置，直接用 block = col / 3 + (row / 3) * 3 就可以代表一个具体 block.

rows[i][num] = cols[j][num] = blocks[k][num] = true;

另外一个很重要的一点是，不是每条 dfs 的搜索都会返回最终的解，因为很多尝试最后会进入死胡同无法解出来，因此每一层 dfs 不能只是单纯的 void 不返回任何值，而是要返回 true / false 代表这条路线走下去是否能得到正确答案。

 public class Solution {
    public void solveSudoku(char[][] board) {
        boolean[][] rows = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        boolean[][] blocks = new boolean[9][9];

        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.'){
                    int num = board[i][j] - '1';
                    int k = j / 3 + (i / 3) * 3;
                    rows[i][num] = cols[j][num] = blocks[k][num] = true;
                }
            }
        }

        dfs(0, board, rows, cols, blocks);
    }

    private boolean dfs(int index, char[][] board, boolean[][] rows, 
                     boolean[][] cols, boolean[][] blocks){
        if(index == 81) return true;
        int row = index / 9;
        int col = index % 9;
        int block = col / 3 + (row / 3) * 3;

        if(board[row][col] != '.') {
            return dfs(index + 1, board, rows, cols, blocks);
        } else {
            for(char chr = '1'; chr <= '9'; chr ++){
                int num = chr - '1';
                if(!rows[row][num] && !cols[col][num] && !blocks[block][num]){
                    board[row][col] = chr;
                    rows[row][num] = true;
                    cols[col][num] = true;
                    blocks[block][num] = true;

                    if(dfs(index + 1, board, rows, cols, blocks)) return true;

                    board[row][col] = '.';
                    rows[row][num] = false;
                    cols[col][num] = false;
                    blocks[block][num] = false;
                }
             }
        }

        return false;
    }
}