// SUDOKU SOLVER
// 2013/02/11 ToMo Star Blog
#include <stdio.h>
#include <stdlib.h>
// http://ja.wikipedia.org/wiki/%E6%95%B0%E7%8B%AC
#define BAN_SIZE 9
#define SQR_SIZE 3
int ban[BAN_SIZE][BAN_SIZE]=
{
{5,3,0,0,7,0,0,0,0},
{6,0,0,1,9,5,0,0,0},
{0,9,8,0,0,0,0,6,0},
{8,0,0,0,6,0,0,0,3},
{4,0,0,8,0,3,0,0,1},
{7,0,0,0,2,0,0,0,6},
{0,6,0,0,0,0,2,8,0},
{0,0,0,4,1,9,0,0,5},
{0,0,0,0,8,0,0,7,9}
};
void print()
{
for(int i=0; i<BAN_SIZE; i++){
for(int j=0; j<BAN_SIZE; j++){
printf(" %d", ban[i][j]);
if((j+1)%SQR_SIZE==0)
printf("|");
}
printf("\n");
if((i+1)%SQR_SIZE==0){
for(int j=0; j<BAN_SIZE; j++)
if((j+1)%SQR_SIZE==0)
printf("+");
else
printf("---");
printf("\n");
}
}
}
int empty(int* x, int* y)
{
for(int i=0; i<BAN_SIZE; i++)
for(int j=0; j<BAN_SIZE; j++)
if( ban[i][j] == 0 ){
*x = i;
*y = j;
return 1;
}
return 0;
}
int find_number(int x, int y, int n)
{
//horizontal
for(int i=0; i<BAN_SIZE; i++)
if( ban[i][y] == n)
return 1;
//vertical
for(int j=0; j<BAN_SIZE; j++)
if( ban[x][j] == n)
return 1;
//square
int x0 = (x/SQR_SIZE)*SQR_SIZE;
int y0 = (y/SQR_SIZE)*SQR_SIZE;
for(int i=0; i<SQR_SIZE; i++)
for(int j=0; j<SQR_SIZE; j++)
if(ban[x0+i][y0+j] == n)
return 1;
//diagonal
//if( x==y )
// for(int k=0; k<BAN_SIZE; k++)
// if( ban[k][k] == n)
// return 1;
//if( BAN_SIZE-x-1==y )
// for(int k=0; k<BAN_SIZE; k++)
// if( ban[BAN_SIZE-k-1][k] == n)
// return 1;
return 0;// not found
}
int solve()
{
int x, y;
if(empty(&x,&y)){
for(int k=1; k<=BAN_SIZE; k++){
if( find_number(x,y, k)==0 ){
// not found
ban[x][y] = k;//tentative
if( solve() )
return 1;
ban[x][y] = 0;
}
}
return 0;
}else
return 1;
}
int solve_all()
{
int x, y;
if(empty(&x,&y)){
for(int k=1; k<=BAN_SIZE; k++){
if( find_number(x,y, k)==0 ){
// not found
ban[x][y] = k;//tentative
solve_all();
ban[x][y] = 0;
}
}
return 0;
}else{
print();
return 1;
}
}
void main()
{
/*
if(solve())
print();
else
printf("No solution!\n");
*/
solve_all();
}
|