#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
struct Sudoku {
private:
int blk[9], row[9], col[9];
int A[9][9], lg[1024];
int lowbit(int x) { /// 得到最低二進制位
return x & (-x);
}
int BLK(int i, int j) { /// 計算某個位置所在的塊
return (i/3)*3 + (j/3);
}
std::vector<std::pair<int, int> > pos; /// 記錄需要處理的位置
void DFS(int d) { /// 填數
if(d == pos.size()) {
for(int i = 0; i <= 8; i ++) {
for(int j = 0; j <= 8; j ++) {
printf("%d ", A[i][j]);
}
putchar('\n');
}
putchar('\n');
}else {
int x = pos[d].first, y = pos[d].second;
int avai = row[x] & col[y] & blk[BLK(x, y)];
while(avai) {
int n = lowbit(avai); /// 找到最低位元并嘗試
avai ^= n;
n = lg[n]; /// 找到對應的數字
A[x][y] = n;
blk[BLK(x, y)] ^= (1<<(n-1));
row[x] ^= (1<<(n-1));
col[y] ^= (1<<(n-1));
DFS(d + 1); /// 遞回選擇下一個位置
A[x][y] = 0;
blk[BLK(x, y)] ^= (1<<(n-1));
row[x] ^= (1<<(n-1));
col[y] ^= (1<<(n-1));
}
}
}
public:
Sudoku() {
for(int i = 1; i <= 9; i ++) { /// 預處理取對數
lg[1<<(i-1)] = i;
}
for(int i = 0; i <= 8; i ++) {
blk[i] = row[i] = col[i] = 0;
}
for(int i = 0; i < 8; i ++) {
for(int j = 0; j < 8; j ++) {
A[i][j] = 0;
}
}
}
int Solve(int B[9][9]) { /// B[i][j] = 0 表示該位置沒有數
for(int i = 0; i <= 8; i ++) {
for(int j = 0; j <= 8; j ++) { /// 坐標 [0, 8]
A[i][j] = B[i][j];
if(A[i][j] != 0) {
blk[BLK(i, j)] |= (1 << (A[i][j]-1));
row[i] |= (1 << (A[i][j]-1));
col[j] |= (1 << (A[i][j]-1)); /// 處理行列和塊
/// col[j] 寫成了 col[i] 除錯了一天 qwq
}else {
pos.push_back(std::make_pair(i, j));
}
}
}
for(int i = 0; i <= 8; i ++) {
blk[i] = ((1<<9)-1) ^ blk[i]; /// 取反
row[i] = ((1<<9)-1) ^ row[i];
col[i] = ((1<<9)-1) ^ col[i];
}
DFS(0);
return 0;
}
};
int B[9][9];
int main() {
Sudoku* tmp = new Sudoku;
for(int i = 0; i <= 8; i ++) {
for(int j = 0; j<= 8; j ++) {
scanf("%d", &B[i][j]);
}
}
tmp -> Solve(B);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/271626.html
標籤：區塊鏈
上一篇：Tencent Server Web的介紹及私有部署
下一篇：關于區塊鏈橢圓曲線加密演算法