# 解数独

<p>编写一个程序，通过填充空格来解决数独问题。</p>
<p>数独的解法需<strong> 遵循如下规则</strong>：</p>
<ol>
    <li>数字 <code>1-9</code> 在每一行只能出现一次。</li>
    <li>数字 <code>1-9</code> 在每一列只能出现一次。</li>
    <li>数字 <code>1-9</code> 在每一个以粗实线分隔的 <code>3x3</code> 宫内只能出现一次。（请参考示例图）</li>
</ol>

<p>数独部分空格内已填入了数字，空白格用 <code>'.'</code> 表示。</p>
<p><strong>示例：</strong></p><img
    src="https://img-blog.csdnimg.cn/img_convert/ed59800c64b76b1efa62aa77747f5330.png#pic_center" />
            
<strong>输入：</strong>

```
board = 
    [["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]]
```

<strong><br />输出：</strong>

```
    [["5","3","4","6","7","8","9","1","2"],
    ["6","7","2","1","9","5","3","4","8"],
    ["1","9","8","3","4","2","5","6","7"],
    ["8","5","9","7","6","1","4","2","3"],
    ["4","2","6","8","5","3","7","9","1"],
    ["7","1","3","9","2","4","8","5","6"],
    ["9","6","1","5","3","7","2","8","4"],
    ["2","8","7","4","1","9","6","3","5"],
    ["3","4","5","2","8","6","1","7","9"]]
```

<strong><br />解释：</strong>输入的数独如上图所示，唯一有效的解决方案如下所示：

<img src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0037.Sudoku%20Solver/images/250px-sudoku-by-l2g-20050714_solutionsvg.png"
    style="height:250px; width:250px" />

<p><strong>提示：</strong></p>
<ul>
    <li><code>board.length == 9</code></li>
    <li><code>board[i].length == 9</code></li>
    <li><code>board[i][j]</code> 是一位数字或者 <code>'.'</code></li>
    <li>题目数据 <strong>保证</strong> 输入数独仅有一个解</li>
</ul>
        
<p>以下<span style="color:red">错误</span>的选项是？</p>


## 答案

```c
class Solution
{
public:
    int row[9][9] = {0}, column[9][9] = {0}, grid[9][9] = {0};
    void generate(int i, int j, vector<vector<char>> &board, bool &selved)
    {
        if (i > 8)
        {
            selved = true;
            return;
        }
        if (board[i][j] == '.')
        {
            int n = 3 * (i / 3) + j / 3;
            for (int k = 0; k < 9; k++)
            {
                if (!row[i][k] && !column[j][k] && !grid[n][k])
                {
                    row[i][k]++;
                    column[j][k]++;
                    grid[n][k]++;
                    board[i][j] = k + '0' + 1;
                    if (j == 8)
                        generate(i + 1, 0, board, selved);
                    else
                        generate(i, j + 1, board, selved);
                    if (!selved)
                    {
                        row[i][k]--;
                        column[j][k]--;
                        grid[n][k]--;
                        board[i][j] = '.';
                    }
                }
            }
        }
        else
        {
            if (j == 8)
                generate(i + 1, 0, board, selved);
            else
                generate(i, j + 1, board, selved);
        }
    }

    void solveSudoku(vector<vector<char>> &board)
    {
        int i, j;
        for (i = 0; i < 9; i++)
        {
            for (j = 0; j < 9; j++)
            {
                if (board[i][j] == '.')
                    continue;
                int num = board[i][j] - '0' - 1;
                row[i][num]++;
                column[j][num]++;
                grid[3 * (i % 3) + j % 3][num]++;
            }
        }
        bool selved = false;
        generate(0, 0, board, selved);
    }
};
```
## 选项


### A

```c
class Solution
{
public:
	void solveSudoku(vector<vector<char>> &board)
	{
		int size = board.size();
		vector<vector<bool>> rows(size, vector<bool>(10));
		vector<vector<bool>> cols(size, vector<bool>(10));
		vector<vector<bool>> boxes(size, vector<bool>(10));
		for (int i = 0; i < size; i++)
		{
			for (int j = 0; j < size; j++)
			{
				if (board[i][j] != '.')
				{
					int num = board[i][j] - '0';
					int idx = i / 3 * 3 + j / 3;
					rows[i][num] = true;
					cols[j][num] = true;
					boxes[idx][num] = true;
				}
			}
		}
		dfs(board, 0, rows, cols, boxes);
	}
private:
	bool valid(int num, int row, int col, int idx, vector<vector<bool>> &rows,
			   vector<vector<bool>> &cols, vector<vector<bool>> &boxes)
	{
		return !rows[row][num] && !cols[col][num] && !boxes[idx][num];
	}
	bool dfs(vector<vector<char>> &board, int size, vector<vector<bool>> &rows,
			 vector<vector<bool>> &cols, vector<vector<bool>> &boxes)
	{
		if (size == 9 * 9)
		{
			return true;
		}
		else
		{
			bool ok = false;
			int row = size / 9;
			int col = size % 9;
			int idx = row / 3 * 3 + col / 3;
			if (board[row][col] == '.')
			{
				for (int i = 1; i <= 9; i++)
				{
					if (valid(i, row, col, idx, rows, cols, boxes))
					{
						board[row][col] = i + '0';
						rows[row][i] = true;
						cols[col][i] = true;
						boxes[idx][i] = true;
						ok = dfs(board, size + 1, rows, cols, boxes);
						if (!ok)
						{
							rows[row][i] = false;
							cols[col][i] = false;
							boxes[idx][i] = false;
							board[row][col] = '.';
						}
					}
				}
			}
			else
			{
				ok = dfs(board, size + 1, rows, cols, boxes);
			}
			return ok;
		}
	}
};
```

### B

```c
class Solution
{
public:
    void solveSudoku(vector<vector<char>> &board)
    {

        Dfs(board, 0);
    }

private:
    bool flag = false;
    void Dfs(vector<vector<char>> &board, int n)
    {

        if (n > 0 && n <= 81)
            if (!JudgeIsNoWant(board, n - 1))
                return;

        if (n >= 81)
        {
            flag = true;
            return;
        }

        int x = n / 9;
        int y = n % 9;

        if (board[x][y] != '.')
            Dfs(board, n + 1);
        else
        {

            for (int i = 1; i < 10; i++)
            {
                board[x][y] = i + 48;
                Dfs(board, n + 1);
                if (flag == true)
                    return;
                board[x][y] = '.';
            }
        }
    }

    bool JudgeIsNoWant(vector<vector<char>> &board, int n)
    {
        int x = n / 9;
        int y = n % 9;

        for (size_t i = 0; i < 9; i++)
        {
            if (board[x][i] == board[x][y] && i != y)
                return false;
            if (board[i][y] == board[x][y] && i != x)
                return false;
        }

        for (int i = x / 3 * 3; i < x / 3 * 3 + 3; i++)
            for (int j = y / 3 * 3; j < y / 3 * 3 + 3; j++)
                if (board[i][j] == board[x][y] && (i != x || j != y))
                    return false;

        return true;
    }
};
```

### C

```c
class Solution
{
public:
    int row[9][9], col[9][9], block[9][9];
    void solveSudoku(vector<vector<char>> &board)
    {
        for (int i = 0; i < 9; ++i)
        {
            for (int j = 0; j < 9; ++j)
            {
                if (board[i][j] == '.')
                    continue;
                int num = board[i][j] - '1';
                row[i][num] = col[j][num] = block[i / 3 * 3 + j / 3][num] = 1;
            }
        }
        dfs(board, 0, 0);
    }
    bool dfs(vector<vector<char>> &board, int r, int c)
    {
        if (r > 8)
            return true;
        if (board[r][c] == '.')
        {
            for (int i = 0; i < 9; ++i)
            {
                if (row[r][i] || col[c][i] || block[r / 3 * 3 + c / 3][i])
                    continue;
                board[r][c] = i + 1 + '0';
                row[r][i] = col[c][i] = block[r / 3 * 3 + c / 3][i] = 1;

                if (dfs(board, r + (c + 1) / 9, (c + 1) % 9))
                    return true;

                board[r][c] = '.';
                row[r][i] = col[c][i] = block[r / 3 * 3 + c / 3][i] = 0;
            }
        }
        else
            return dfs(board, r + (c + 1) / 9, (c + 1) % 9);
        return false;
    }
};
```