# 解数独

<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> </p>
<div class="top-view__1vxA">
    <div class="original__bRMd">
        <div>
            <p><strong>示例：</strong></p><img
                src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0037.Sudoku%20Solver/images/250px-sudoku-by-l2g-20050714svg.png" />
            <pre><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>输出：</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>解释：</strong>输入的数独如上图所示，唯一有效的解决方案如下所示：
<p> </p>   
</pre>
            <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> </p>
            <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>
        </div>
    </div>
</div>

以下程序实现了这一功能，请你填补空白处的内容：

```cpp
#include <bits/stdc++.h>
using namespace std;
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;
                        _______________________________;
                        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;
        }
    }
};
```

## template

```cpp
#include <bits/stdc++.h>
using namespace std;
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;
        }
    }
};
```

## 答案

```cpp
ok = dfs(board, size + 1, rows, cols, boxes);
```

## 选项

### A

```cpp
ok = dfs(board, size - 1, rows, cols, boxes);
```

### B

```cpp
ok = dfs(board, size, rows, cols, boxes);
```

### C

```cpp
ok = dfs(board, size, rows + 1, cols - 1, boxes);
```