65 lines
1.7 KiB
C++
65 lines
1.7 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 4; // 4阶数独
|
||
int n = N * N; //总个数
|
||
|
||
int b1[N][N]; //行的桶,行：第几行，列：哪个数字，值：是否出现过
|
||
int b2[N][N]; //列的桶,行：第几列，列：哪个数字，值：是否出现过
|
||
int b3[N][N]; //块的桶,行：第几块，列：哪个数字，值：是否出现过
|
||
|
||
const int M = 10; //数组的长度，开大一点
|
||
int a[M * M]; //二维降为一维
|
||
int ans;
|
||
|
||
void dfs(int x) {
|
||
//边界,递归出口
|
||
if (x == n + 1) {
|
||
//计数增加1
|
||
ans++;
|
||
// 输出方案
|
||
for (int i = 1; i <= n; i++) {
|
||
printf("%d ", a[i]);
|
||
if (i % N == 0) cout << endl; //换行符
|
||
}
|
||
cout << endl; //换行符
|
||
return;
|
||
}
|
||
|
||
//一维转化为二维的套路，计算出如果在二维数组情况下的行和列
|
||
int row = (x - 1) / N + 1; //横行编号
|
||
int col = (x - 1) % N + 1; //竖排编号
|
||
|
||
//小块编号
|
||
int block;
|
||
if (row <= 2 && col <= 2)
|
||
block = 1;
|
||
else if (row <= 2 && col > 2)
|
||
block = 2;
|
||
else if (row > 2 && col <= 2)
|
||
block = 3;
|
||
else if (row > 2 && col > 2)
|
||
block = 4;
|
||
|
||
for (int i = 1; i <= N; i++) {
|
||
//如果i这个数字，在行，列，块中都没有出现过，可以填充上
|
||
if (!b1[row][i] && !b2[col][i] && !b3[block][i]) {
|
||
//填充
|
||
a[x] = i;
|
||
//标识为已使用
|
||
b1[row][i] = b2[col][i] = b3[block][i] = 1;
|
||
//递归计算下一个
|
||
dfs(x + 1);
|
||
//回溯
|
||
b1[row][i] = b2[col][i] = b3[block][i] = 0;
|
||
}
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
//从第1个开始填充
|
||
dfs(1);
|
||
//输出大吉
|
||
printf("%d", ans);
|
||
return 0;
|
||
} |