# 解数独

<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://img-service.csdnimg.cn/img_convert/ed59800c64b76b1efa62aa77747f5330.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://img-service.csdnimg.cn/img_convert/3d74b48c1652fc4320bc5986162756f0.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>

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

```java
class Solution {

	boolean row[][] = new boolean[9][9];
	boolean col[][] = new boolean[9][9];

	boolean cell[][][] = new boolean[3][3][9];

	public void solveSudoku(char[][] board) {

		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				if (board[i][j] != '.') {

					int t = board[i][j] - '1';

					row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
				}
			}
		}

		dfs(board, 0, 0);
	}

	public boolean dfs(char[][] board, int x, int y) {

		if (y == 9) {

			x++;
			y = 0;
		}

		if (x == 9)
			return true;

        ____________________;

		for (int num = 0; num < 9; num++) {

			if (!row[x][num] && !col[y][num] && !cell[x / 3][y / 3][num]) {

				board[x][y] = (char) (num + '1');
				row[x][num] = col[y][num] = cell[x / 3][y / 3][num] = true;

				if (dfs(board, x, y + 1))
					return true;

				board[x][y] = '.';
				row[x][num] = col[y][num] = cell[x / 3][y / 3][num] = false;
			}
		}

		return false;
	}
}

```


## template

```java
class Solution {

	boolean row[][] = new boolean[9][9];
	boolean col[][] = new boolean[9][9];

	boolean cell[][][] = new boolean[3][3][9];

	public void solveSudoku(char[][] board) {

		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				if (board[i][j] != '.') {

					int t = board[i][j] - '1';

					row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
				}
			}
		}

		dfs(board, 0, 0);
	}

	public boolean dfs(char[][] board, int x, int y) {

		if (y == 9) {

			x++;
			y = 0;
		}

		if (x == 9)
			return true;

		if (board[x][y] != '.')
			return dfs(board, x, y + 1);

		for (int num = 0; num < 9; num++) {

			if (!row[x][num] && !col[y][num] && !cell[x / 3][y / 3][num]) {

				board[x][y] = (char) (num + '1');
				row[x][num] = col[y][num] = cell[x / 3][y / 3][num] = true;

				if (dfs(board, x, y + 1))
					return true;

				board[x][y] = '.';
				row[x][num] = col[y][num] = cell[x / 3][y / 3][num] = false;
			}
		}

		return false;
	}
}

```

## 答案

```java
if (board[x][y] != '.')
    return dfs(board, x, y + 1);
```

## 选项

### A

```java
if (board[x][y] != '.')
    return dfs(board, x, y);
```

### B

```java
if (board[x][y] == '.')
    return dfs(board, x, y);
```

### C

```java
if (board[x][y] == '.')
    return dfs(board, x, y + 1);
```