数独是源自18世纪瑞士的一种数学游戏,它是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据 9 × 9 盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫内的数字均含 1 - 9,不重复。本题给你一个填好的数独,请你验证一下该数独是否正确(满足每一行、每一列、每一个粗线宫内的数字均含 1 - 9)。 小E觉得这个问题很简单,所以他偷偷交换了数独两个宫的位置(也可能没换)。现在,请你使用C++语言,编写一段代码来判断给出的数独是否可以通过交换或不换其中两个宫内的对应数字使得数独正确。代码要求简洁易懂。
时间: 2023-05-27 10:03:06 浏览: 66
思路:
先通过判断每一行、每一列、每一个粗线宫内的数字是否含 1 - 9、是否有重复数字来判断原数独是否正确。
然后交换或不换两个宫(行或列中任意两个宫),再次进行验证。如果可以使得验证结果正确,则说明原数独可以通过交换或不换两个宫内的对应数字使得数独正确。
代码实现:
```
#include <stdio.h>
#define N 9 // 数独维度
#define M 3 // 宫格维度
#define swap(x, y) { typeof(x) temp = x; x = y; y = temp; } // 宏定义函数实现交换
int grid[N][N]; // 数独矩阵
// 判断是否在某行中出现过某数字
int in_row(int row, int num) {
int i;
for (i = 0; i < N; ++i)
if (grid[row][i] == num)
return 1;
return 0;
}
// 判断是否在某列中出现过某数字
int in_col(int col, int num) {
int i;
for (i = 0; i < N; ++i)
if (grid[i][col] == num)
return 1;
return 0;
}
// 判断是否在某宫中出现过某数字
int in_block(int row, int col, int num) {
int i, j;
for (i = 0; i < M; ++i)
for (j = 0; j < M; ++j)
if (grid[row+i][col+j] == num)
return 1;
return 0;
}
// 判断是否可以放置某数字
int is_valid(int row, int col, int num) {
return !in_row(row, num) && !in_col(col, num) && !in_block(row-row%M, col-col%M, num);
}
// 判断数独是否正确
int is_correct() {
int i, j, num;
// 判断每一行是否合法
for (i = 0; i < N; ++i) {
for (j = 0; j < N; ++j) {
if (grid[i][j] < 1 || grid[i][j] > N || in_row(i, grid[i][j])) {
return 0; // 不合法
}
}
}
// 判断每一列是否合法
for (i = 0; i < N; ++i) {
for (j = 0; j < N; ++j) {
if (grid[j][i] < 1 || grid[j][i] > N || in_col(i, grid[j][i])) {
return 0; // 不合法
}
}
}
// 判断每一个宫是否合法
for (i = 0; i < N; i += M) {
for (j = 0; j < N; j += M) {
for (num = 1; num <= N; ++num) {
if (!is_valid(i, j, num)) {
return 0; // 不合法
}
}
}
}
return 1; // 合法
}
// 判断数独是否可行
int is_solvable() {
int i, j, k, l;
// 尝试交换两个宫的位置(任意两个宫)
for (i = 0; i < N; i += M) {
for (j = 0; j < N; j += M) {
for (k = 0; k < N; k += M) {
for (l = 0; l < N; l += M) {
if (i == k && j == l) continue; // 相同宫格,跳过
swap(grid[i][j], grid[k][l]);
if (is_correct()) {
return 1; // 可行
}
swap(grid[i][j], grid[k][l]);
}
}
}
}
return 0; // 不可行
}
int main() {
int i, j;
// 输入数独
for (i = 0; i < N; ++i) {
for (j = 0; j < N; ++j) {
scanf("%d", &grid[i][j]);
}
}
// 判断数独是否可行
if (is_solvable()) {
printf("YES\n");
} else {
printf("NO\n");
}
return 0;
}
```