Last active
December 17, 2015 18:39
-
-
Save windworst/5655103 to your computer and use it in GitHub Desktop.
sudoku
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#define N 9 | |
#define N_BOX 3 | |
int mat[N][N] = {0}; | |
int mat_set[N][N] = {0}; | |
int g_judge_count = 0; | |
int Judge(int x, int y) | |
{ | |
++g_judge_count; | |
//Line & Cols | |
//if(0) | |
{ | |
int i; | |
int s = mat[y][x]; | |
for(i=0; i < N ; ++i) | |
{ | |
if( (i!=x && s==mat[y][i]) | |
|| (i!=y && s==mat[i][x]) ) | |
{ | |
//printf("y=%d,x=%d\n",y,x); | |
return 0; | |
} | |
} | |
} | |
//Box | |
//if(0) | |
{ | |
int x_start = x / N_BOX * N_BOX; | |
int x_stop = x_start + N_BOX; | |
int y_start = y / N_BOX * N_BOX; | |
int y_stop = y_start + N_BOX; | |
int ix,iy; | |
for(iy=y_start; iy < y_stop; ++iy) | |
{ | |
for(ix=x_start; ix < x_stop; ++ix) | |
{ | |
//printf("ix=%d,iy=%d\n",ix,iy); | |
if( (ix!=x && iy!=y) | |
&& mat[iy][ix]==mat[y][x] | |
) | |
{ | |
return 0; | |
} | |
} | |
} | |
} | |
return 1; | |
} | |
int Input() | |
{ | |
int ix,iy; | |
for(iy=0; iy < N; ++iy) | |
{ | |
for(ix=0; ix < N; ++ix) | |
{ | |
int s; | |
fscanf(stdin,"%d",&s); | |
mat[iy][ix] = mat_set[iy][ix] = s; | |
} | |
} | |
return 0; | |
} | |
int Output() | |
{ | |
int ix,iy; | |
for(iy=0; iy < N; ++iy) | |
{ | |
for(ix=0; ix < N; ++ix) | |
{ | |
printf("%d ",mat[iy][ix]); | |
if( (ix+1)%3==0 )putchar(' '); | |
} | |
printf("\n"); | |
if( (iy+1)%3==0 )putchar('\n'); | |
} | |
return 0; | |
} | |
int Check() | |
{ | |
int i=0; | |
g_judge_count = 0; | |
while(0<=i && i<N*N) | |
{ | |
//printf("%d\n",i); | |
if(mat_set[i/N][i%N]!=0)//Is Set | |
{ | |
++i; | |
continue; | |
} | |
for( ++mat[i/N][i%N]; mat[i/N][i%N]<=N; ++mat[i/N][i%N]) | |
{ | |
if(Judge(i%N,i/N)) | |
{ | |
break; | |
} | |
} | |
if(mat[i/N][i%N]>N) //Not Found | |
{ | |
mat[i/N][i%N] = 0; | |
--i; | |
while(0<=i && mat_set[i/N][i%N]!=0)--i; | |
} | |
else | |
{ | |
++i; | |
} | |
} | |
if(i==N*N) | |
return 1; | |
return 0; | |
} | |
int main() | |
{ | |
Input(); | |
if(Check()) | |
{ | |
Output(); | |
printf("Judge Count = %d\n",g_judge_count); | |
} | |
else | |
{ | |
printf("Not Found\n"); | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment