Drolca

Apologize To Drolca
随笔 - 28, 文章 - 1, 评论 - 6, 引用 - 0
数据加载中……

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 阅读(539) 评论(1)  编辑 收藏 引用

评论

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

不是最快的实现方法
2010-01-03 11:12 | forestkeeper

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理