【题目描述】
In the game of Sudoku, you are given a large 9 × 9 grid divided into smaller 3 × 3 subgrids. For example,
. 2 7 3 8 . . 1 .
. 1 . . . 6 7 3 5
. . . . . . . 2 9
3 . 5 6 9 2 . 8 .
. . . . . . . . .
. 6 . 1 7 4 5 . 3
6 4 . . . . . . .
9 5 1 8 . . . 7 .
. 8 . . 6 5 3 4 .
Given some of the numbers in the grid, your goal is to determine the remaining numbers such that the numbers 1 through 9 appear exactly once in (1) each of nine 3 × 3 subgrids, (2) each of the nine rows, and (3) each of the nine columns.
【题目链接】
【算法】
剪枝+状态压缩常数优化。好难啊。。。。
【代码】
#include <stdio.h>
using namespace std;
char G[10][10];
int row[10],col[10],grid[10],rec[512],num[512];
inline int g(int x,int y) {
return (x/3)*3+y/3;
}
inline void flip(int x,int y,int to) {
row[x]^=1<<to;
col[y]^=1<<to;
grid[g(x,y)]^=1<<to;
}
bool dfs(int cur) {
if(cur==0) return 1;
int minn=10,x,y;
for(int i=0;i<9;i++) {
for(int j=0;j<9;j++) {
if(G[i][j]=='.') {
int val=row[i]&col[j]&grid[g(i,j)];
if(!val) return 0;
if(rec[val]<minn) {
minn=rec[val],x=i,y=j;
}
}
}
}
int val=row[x]&col[y]&grid[g(x,y)];
for(;val;val-=val&-val) {
int to=num[val&-val];
G[x][y]=to+'1';
flip(x,y,to);
if(dfs(cur-1)) return 1;
flip(x,y,to);
G[x][y]='.';
}
return 0;
}
int main() {
for(int i=0;i<1<<9;i++) {
for(int j=i;j;j-=j&-j)
rec[i]++;
}
for(int i=0;i<9;i++) {
num[1<<i]=i;
}
char s[100];
while(~scanf("%s",s)&&s[0]!='e') {
for(int i=0;i<9;i++) row[i]=col[i]=grid[i]=(1<<9)-1;
int tot=0;
for(int i=0;i<9;i++) {
for(int j=0;j<9;j++) {
G[i][j]=s[i*9+j];
if(G[i][j]!='.') flip(i,j,G[i][j]-'1');
else ++tot;
}
}
dfs(tot);
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
s[i*9+j]=G[i][j];
puts(s);
}
return 0;
}