数独

需要满足的条件——

1. 每行/每列数字不能重复
2. 划分为9个九宫格区域后，每个区域内数字不能重复

如何判断每个九宫格内数字不重复呢？以第一个和第二个九宫格为例：

1. (0,0), (0,1), (0,2)｜｜｜(0,3), (0,4), (0,5)
2. (1,0), (1,1), (1,2)｜｜｜(1,3), (1,4), (1,5)
3. (2,0), (2,1), (2,2)｜｜｜(2,3), (2,4), (2,5)

设当前坐标为(x,y)，那么当前九宫格内任意一个位置的坐标为:

1. 横坐标——(x/3)*3 + i/3
2. 纵坐标——(y/3)*3 + i%3
3. 其中i的范围为0..8

另外注意到，解法唯一，我们需要设置提前退出条件，以降低算法的时间复杂度。

完整代码如下：

//
// Created by jt on 2020/9/1.
//
#include <vector>

using namespace std;

class Solution {
public:
    void solveSudoku(vector<vector<char> > &board) {
        dfs(board, 0, 0);
    }

    bool dfs(vector<vector<char> > &board, int x, int y) {
        if (x == 9) { return true; }
        if (y == 9) { return dfs(board, x+1, 0); }  // 跳转到下一行
        if (board[x][y] != '.') { return dfs(board, x, y+1); }
        for (char c = '1'; c <= '9'; ++c) {
            if (!isValid(board, x, y, c)) continue;
            board[x][y] = c;
            if (dfs(board, x, y+1)) return true;
            board[x][y] = '.';
        }
        return false;
    }

    bool isValid(vector<vector<char> > &board, int x, int y, char ch) {
        for (int i = 0; i < 9; ++i) {
            if (board[x][i] == ch) return false;
            if (board[i][y] == ch) return false;
            if (board[(x/3)*3 + i/3][(y/3)*3 + i%3] == ch) return false;
        }
        return true;
    }
};