帮我C++写一个判断数独是否有多解,和一个输出解的函数输出
时间: 2024-05-04 19:18:42 浏览: 9
以下是一个简单的 C++ 实现,用于判断数独是否有多解并输出解:
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 9;
int map[MAXN][MAXN], row[MAXN], col[MAXN], block[MAXN][MAXN], num;
void dfs(int x, int y) {
if (y == 9) {
dfs(x + 1, 0);
return;
}
if (x == 9) {
num++;
return;
}
if (map[x][y]) {
dfs(x, y + 1);
return;
}
for (int i = 1; i <= 9; i++) {
if (!row[x][i] && !col[y][i] && !block[x / 3 * 3 + y / 3][i]) {
row[x][i] = col[y][i] = block[x / 3 * 3 + y / 3][i] = 1;
map[x][y] = i;
dfs(x, y + 1);
if (num > 1) return; // 如果已经有多解了,就直接返回
row[x][i] = col[y][i] = block[x / 3 * 3 + y / 3][i] = 0;
map[x][y] = 0;
}
}
}
void print_map() { // 输出解
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cout << map[i][j] << " ";
}
cout << endl;
}
}
int main() {
// 输入数独
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cin >> map[i][j];
if (map[i][j]) {
row[i][map[i][j]] = 1;
col[j][map[i][j]] = 1;
block[i / 3 * 3 + j / 3][map[i][j]] = 1;
}
}
}
dfs(0, 0);
if (num == 1) {
cout << "Unique Solution" << endl;
print_map();
} else {
cout << "Multiple Solutions" << endl;
}
return 0;
}
```
其中,`dfs()` 函数用于深度优先搜索数独的解,如果搜索到一个解,就将全局变量 `num` 加一,如果 `num` 大于 1,则说明有多解,直接返回即可。`print_map()` 函数用于输出解,可以在搜索到唯一解之后调用。