题目出处 http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=2676
Sudoku
Time Limit:2000MS Memory Limit:65536K
Total Submit:561 Accepted:293 Special Judged
Description
Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3x3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3x3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task.
Input
The input data will start with the number of the test cases. For each test case, 9 lines follow, corresponding to the rows of the table. On each line a string of exactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0.
Output
For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. If solutions is not unique, then the program may print any one of them.
Sample Input
1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
Sample Output
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127
Source
Southeastern Europe 2005
//----------------------------------------------------------
题目大意：在九宫(3×3的格子)里可以填入1~9这9个数字之一，要求填完这9个九宫后每行没列不能出现相同的数字.数独又称“九宫格”。是当今欧美、日本、韩国,台湾等地的媒体、网络等都在极力推荐的无比有趣且令人着迷的游戏。 “数独”一词来自日文,但概念源自拉丁方块,由十八世纪瑞士数学家欧拉发明。
//test.cpp
#include <stdio.h>
#include <windows.h>
#include <conio.h>
#include <assert.h>
int ni[9][9]=
{1,0,3,0,0,0,5,0,9,
0,0,2,1,0,9,4,0,0,
0,0,0,7,0,4,0,0,0,
3,0,0,5,0,2,0,0,6,
0,6,0,0,0,0,0,5,0,
7,0,0,8,0,3,0,0,4,
0,0,0,4,0,1,0,0,0,
0,0,9,2,0,5,8,0,0,
8,0,4,0,0,0,1,0,7};
int ns[9][9]={0,};
int no[9][9];
int cBin0(int n)
{
int ret=0;
for(int i=0;i<9;i++)
ret +=( (n&((1<<i))) ==0);
return ret;
}
int find1()
{
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(ns[i][j]>>16==1)
{
for(int k=0;k<9;k++)
{
if(ns[i][j]>>16)
{
int x=ns[i][j] & (1<<k);
if(!x )
return (i<<8)+(j<<4)+k+1;
}
}
}
}
}
return 0;
}
void fill1(int pos)
{
int i=(pos>>8);
int j=(pos>>4) &0x0f;
no[i][j] = pos&0x0f;
}
int check()
{
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
if(ns[i][j]&0x1ff)
return 1;
}
}
return 0;
}
int setState()
{
int c=0,m,n;
memset(ns,0,sizeof(ns));
for(int i=0;i<9;i++)
{
m=i/3*3;
for(int j=0;j<9;j++)
{
n=j/3*3;
if(no[i][j])
{
ns[i][j]=0x1ff;
c++;
}
else
{
ns[i][j] =0;
for(int k=0;k<9;k++)
{
ns[i][j] |= ((1<<no[i][k])>>1);
ns[i][j] |= ((1<<no[k][j])>>1);
ns[i][j] |= ((1<<no[m+k/3][n+k%3])>>1);
}
ns[i][j] |= cBin0(ns[i][j])<<16;
}
}
}
return c;
}
void pArr(int p[9][9])
{
for(int i=0;i<9;i++)
{
for(int j=0;j<9;j++)
{
printf("%x ",(int)p[i][j]);
if(j%3==2)
printf("\t");
}
printf("\n");
if(i%3==2)
printf("\n");
}
}
int main()
{
printf("input:\n");
pArr(ni);
unsigned int t1=GetTickCount();
int i,m;
memcpy(no,ni,sizeof(no));
setState();
// pArr(ns);
while(check())
{
// pArr(ni);
if(i=find1())
{
m=(i&0xf);
if( m>=10 || m<1)
{
printf("ERR: %x\n",i);
assert(0);
}
fill1(i);
m=setState();
printf("current filled:%d\n",m);
printf("no[%d][%d]=%d\n",(i>>8),((i>>4)&0xf),(i&0xf));
pArr(no);
// pArr(ns);
getch();
}
else
break;
}
unsigned int t2=GetTickCount();
// printf("time used: %d ms\noutput:\n",t2-t1);
printf("output:\n");
pArr(no);
return 0;
}