36. Valid Sudoku

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 用于定位 block，i 对应第 i 个子矩阵。

k 从0到8，代表子矩阵内第 k 个格子。 实现对于每一个子矩阵的格子 (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 tmp = board[i][j] - '1';
                    if (row[tmp]) return false;
                    row[tmp] = true;
                }
                if (board[j][i] != '.') {
                    int tmp = board[j][i] - '1';
                    if (col[tmp]) return false;
                    col[tmp] = 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 tmp = board[x][y] - '1';
                    if (cell[tmp]) return false;
                    cell[tmp] = true;
                }
            }
        }
        return true;
    }
}

37. Sudoku Solver