Drolca

Apologize To Drolca

9*9数独游戏

#include <iostream>
using namespace std;
const int M=10;
bool userow[M][M],usecol[M][M],useblock[M][M];
int map[M][M];

struct node{

int x,y;

int num;
}
sudu[M*M];

int find(int x,int y)
{

int row=x/3;

int col=y/3;

return 3*row+col;
}

bool dfs(int n,int cnt)
{

if(n==cnt)return 1;

int i;

for(i=1;i<M;i++)

{

if(!userow[sudu[n].x][i]&&!usecol[sudu[n].y][i]&&!useblock[find(sudu[n].x,sudu[n].y)][i])

{
userow[sudu[n].x][i]
=true;
usecol[sudu[n].y][i]
=true;
useblock[find(sudu[n].x,sudu[n].y)][i]
=true;
sudu[n].num
=i;

if(dfs(n+1,cnt))

return 1;
userow[sudu[n].x][i]
=false;
usecol[sudu[n].y][i]
=false;
useblock[find(sudu[n].x,sudu[n].y)][i]
=false;
sudu[n].num
=0;

}

}

return 0;

}

int main()
{

int T;
scanf(
"%d",&T);

while(T--)

{
memset(userow,
false,sizeof(userow));
memset(usecol,
false,sizeof(usecol));
memset(useblock,
false,sizeof(useblock));

int i,j;

int cnt=0;

for(i=0;i<M-1;i++)

{

char mess[M];
scanf(
"%s",&mess);

for(j=0;j<M-1;j++)

{
map[i][j]
=mess[j]-'0';

if(map[i][j])

{
userow[i][map[i][j]]
=true;
usecol[j][map[i][j]]
=true;
useblock[find(i,j)][map[i][j]]
=true;
}

else

{
sudu[cnt].x
=i;
sudu[cnt].y
=j;
sudu[cnt].num
=0;
cnt
++;
}

}

}

dfs(
0,cnt);

for(i=0;i<cnt;i++)
map[sudu[i].x][sudu[i].y]
=sudu[i].num;

for(i=0;i<M-1;i++){

for(j=0;j<M-1;j++)
printf(
"%d",map[i][j]);
printf(
"\n");
}

}

return 0;
}

posted on 2010-01-01 21:19 Drolca 阅读(469) 评论(1)  编辑 收藏 引用

#re: 9*9数独游戏回复更多评论

2010-01-03 11:12 | forestkeeper