数独游戏
数独是一种数学逻辑游戏，游戏由9×9个格子组成，玩家需要根据格子提供的数字推理出其他格子的数字。游戏设计者会提供最少17个数字使得解答谜题只有一个答案。
这种游戏只需要逻辑思维能力，与数字运算无关。虽然玩法简单，但提供的数字却千变万化，所以不少教育者认为数独是锻炼脑筋的好方法。
数独游戏由日本游戏公司 Nikoli 于 1986年 发明，意思为“独身最适数字”
求解数独
数独的求解非常简单，只需要保证9×9的格子中，每一个竖行，横行，子3×3格子中的数字都由1-9组成，且在这三个子区间内，不能重复数字，一般来说，求解数独的过程是一个不断尝试并修改的过程。
回溯算法
回溯算法就是一个不断枚举和碰撞的过程，在不断尝试合法解的过程中，遇到不满足即返回重新求解，直到整个路径全部合法。本数独求解算法便是学习回溯算法的内涵而完成的。
以下算法由C++实现
问题拆分
求解数独的目的即在将81个数字填入9×9的方格，且满足数独规则。要填满9×9则需要每一行，每一列，每个子格都满足规则，则我们便有如下的检测方法。
- 检测数字是否已经在横行使用过
bool alreadyInRow(int grid[LENGTH][LENGTH], int row, int num) {
for (int col = 0; col < LENGTH; col++)
if (grid[row][col] == num) {
return true;
}
return false;
}
- 检测数字是否已经在竖行使用过
bool alreadyInCol(int grid[LENGTH][LENGTH], int col, int num) {
for (int row = 0; row < LENGTH; row++)
if (grid[row][col] == num) {
return true;
}
return false;
}
- 检测是否在子格(3×3)使用过
bool alreadyInSubgrid(int grid[LENGTH][LENGTH], int startRow, int startCol, int num) {
for (int row = 0; row < 3; row++)
for (int col = 0; col < 3; col++)
if (grid[row + startRow][col + startCol] == num) {
return true;
}
return false;
}
这里需要注意的是 startRow, startCol 是由当前所填数字位置通过计算得到的其所处子格的起始格的位置(有点绕，多读几遍)。
最后我们将这三种检测合并可得 isValid() 函数
bool isValid(int grid[LENGTH][LENGTH], int row, int col, int num) {
return !alreadyInRow(grid, row, num) &&
!alreadyInCol(grid, col, num) &&
!alreadyInSubgrid(grid, row - row % 3, col - col % 3, num);
}
row - row % 3, col - col % 3 便是我们如何得到所处子格的起始格的位置的方法，例如检测位置为 2，1，通过计算得0，0，则应该在左上角那个子格进行检测。
好的，到这里我们已经做完80%了，what？是的，回溯算法就是如此的简洁。
下面我们来思考最后的求解思路
- 判断所有格子是否已被填满
- 得到未被填入数字的格子位置
- 我们将1-9依次尝试，通过上面的检测方法进行检测，若通过则我们则继续寻找下一个未被填入数字的格子，若没有通过则将其设置为0，继续尝试。
先补充一个得到空格子的方法
pair<int, int> getUnusedLocation(int grid[LENGTH][LENGTH]) {
for (int row = 0; row < LENGTH; row++)
for (int col = 0; col < LENGTH; col++)
if (grid[row][col] == 0) {
return make_pair(row, col);
}
return COMPLETED;
}
循环遍历所有格子即可，返回第一个没有被填入数字(这里用0替代)的对组。
最后我们的 solve() 函数可以得到
bool solve(int grid[LENGTH][LENGTH]) {
if (getUnusedLocation(grid) == COMPLETED) {
return true;
}
pair<int, int> position = getUnusedLocation(grid);
int row = position.first;
int col = position.second;
for (int num = 1; num <= 9; num++) {
if (isValid(grid, row, col, num)) {
grid[row][col] = num;
if (solve(grid)) {
return true;
}
grid[row][col] = 0;
}
}
return false;
}
使用
我们先编写主函数
int main() {
cout << "Sodoku" << endl;
int grid[LENGTH][LENGTH] = {{5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9}};
bool result{false};
clock_t start, finish;
double total;
print(grid);
start = clock();
result = solve(grid);
finish = clock();
total = (double) (finish - start) / CLOCKS_PER_SEC;
if (result) {
print(grid);
cout << "total time: " << total << "s" << endl;
} else {
cout << "dead sodoku" << endl << endl;
}
return 0;
}
我们同时加入了运行时间检测的功能
输入
------------------------------------
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 |
------------------------------------
输出
------------------------------------
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 |
------------------------------------
例子
运行时间 (本机)：total time: 0.003135s
