# 解数独

<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>

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

```python
class Solution(object):
	def solveSudoku(self, board):
			def isvaild(i,j):
				for m in range(9):
					if m!=i and board[m][j]==board[i][j]:
						return False
				for n in range(9):
					if n!=j and board[i][n]==board[i][j]:
						return False
				______________________;
				return True
			def f(a,b,board):
				for i in range(a,9):
					for j in range(b,9):
						if board[i][j]=='.':
							for c in '123456789':
								board[i][j]=c
								if isvaild(i,j):
									if f(a,b,board):return True
									else: board[i][j] = '.'
								else:board[i][j] = '.'
							return False
				return True
			f(0,0,board)
			return board
# %%
s = Solution()
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"]]
print(s.solveSudoku(board))
```

## template

```python
class Solution(object):
	def solveSudoku(self, board):
			def isvaild(i,j):
				for m in range(9):
					if m!=i and board[m][j]==board[i][j]:
						return False
				for n in range(9):
					if n!=j and board[i][n]==board[i][j]:
						return False
				for m in range(i//3*3,i//3*3+3):
					for n in range(j//3*3,j//3*3+3):
						if m!=i and n!=j and board[m][n]==board[i][j]:
							return False
				return True
			def f(a,b,board):
				for i in range(a,9):
					for j in range(b,9):
						if board[i][j]=='.':
							for c in '123456789':
								board[i][j]=c
								if isvaild(i,j):
									if f(a,b,board):return True
									else: board[i][j] = '.'
								else:board[i][j] = '.'
							return False
				return True
			f(0,0,board)
			return board
# %%
s = Solution()
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"]]
print(s.solveSudoku(board))
```

## 答案

```python
for m in range(i//3*3,i//3*3+3):
    for n in range(j//3*3,j//3*3+3):
        if m!=i and n!=j and board[m][n]==board[i][j]:
            return False
```

## 选项

### A

```python
for m in range(i//3*3,i//3*3+3):
    for n in range(j//3*3,j//3*3+3):
        if board[m][n]==board[i][j]:
            return False
```

### B

```python
for m in range(i//3*3,i//3*3+3):
    for n in range(j//3*3,j//3*3+3):
        if m==i and n==j and board[m][n]==board[i][j]:
            return False
```

### C

```python
for m in range(i//3*3,i//3*3+3):
    for n in range(j//3*3,j//3*3+3):
        if board[m][n]==board[i][j]:
            return True
```