题目链接：解数独
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
- 数字
1-9 在每一行只能出现一次。
- 数字
1-9 在每一列只能出现一次。
- 数字
1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。
一个数独。
答案被标成红色。
Note:
- 给定的数独序列只包含数字
1-9 和字符 '.' 。
- 你可以假设给定的数独只有唯一解。
- 给定数独永远是
9x9 形式的。
思路
经典的解数独游戏。
首先记录下来所有的需要填数字的坐标信息，然后从第一个需要填数的地方开始填数，依次判断数字 1-9 ，当前位置是否可以填数，可以的话填数，继续搜索下一层，最后回溯的时候需要取消填数继续试。如果找到答案，就记录一下，这里可以剪枝。
要判断一个地方能不能填数字，要满足：
- 这一行中有没有相同数字
- 这一列中有没有相同数字
- 当前的小9宫格中，有没有相同数字（对当前坐标
*3和/3的操作是为了确定当前小九宫格的起始点坐标）
如果满足这个条件，证明这个地方可以填数。
具体看代码
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
class Solution
{
public:
vector<pair<int, int>> point;
vector<vector<char>> ans;
bool flag;
bool check(vector<vector<char>> &board, int k, int step)
{
for (int i = 0; i < 9; i++)
if (board[point[step].first][i] - '0' == k || board[i][point[step].second] - '0' == k)
return false;
// 计算当前所在的小九宫格坐标
int x = (point[step].first / 3) * 3;
int y = (point[step].second / 3) * 3;
for (int i = x; i < x + 3; i++)
for (int j = y; j < y + 3; j++)
if (board[i][j] - '0' == k)
return false;
return true;
}
void dfs(vector<vector<char>> &board, int step)
{
if (flag)
return;
if (step == point.size())
{
flag = true;
ans = board;
return;
}
for (int i = 1; i <= 9; i++)
{
if (check(board, i, step))
{
board[point[step].first][point[step].second] = i + '0';
dfs(board, step + 1);
board[point[step].first][point[step].second] = '.';
}
}
}
void solveSudoku(vector<vector<char>> &board)
{
flag = false;
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
if (board[i][j] == '.')
point.push_back({i, j});
dfs(board, 0);
board = ans;
}
};
|
最后修改于 2020-09-15
本作品采用
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。