#include <stdio.h>
#define SIZE 3
#define ROW_SIZE (SIZE*SIZE)
#define COL_SIZE (SIZE*SIZE)
#define CAND_SIZE (SIZE*SIZE)
#define ND 0
typedef enum BOOL{FALSE,TRUE} bool;
bool solve(int*);
bool dfs(int*,int);
void get_cand(bool*,int*,int);
void print_board(int*);
int main(){
int board[]={
0, 0, 0, 0, 0, 0, 0, 1, 0,
4, 0, 0, 0, 0, 0, 0, 0, 0,
0, 2, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 5, 0, 4, 0, 7,
0, 0, 8, 0, 0, 0, 3, 0, 0,
0, 0, 1, 0, 9, 0, 0, 0, 0,
3, 0, 0, 4, 0, 0, 2, 0, 0,
0, 5, 0, 1, 0, 0, 0, 0, 0,
0, 0, 0, 8, 0, 6, 0, 0, 0
/*
0, 0, 0, 0, 3, 0, 13, 0, 0, 0, 0, 6, 10, 18, 17, 11, 0, 14, 0, 20, 0, 9, 0, 24, 22,
4, 0, 0, 17, 13, 0, 8, 21, 0, 0, 0, 12, 23, 0, 20, 10, 2, 1, 3, 0, 0, 15, 16, 19, 0,
0, 5, 0, 11, 7, 0, 0, 6, 15, 16, 0, 3, 2, 0, 0, 12, 0, 22, 9, 0, 0, 0, 25, 0, 18,
0, 8, 18, 16, 0, 14, 0, 0, 0, 23, 0, 1, 0, 24, 0, 19, 0, 0, 17, 21, 0, 0, 0, 0, 11,
14, 0, 23, 0, 0, 3, 0, 0, 25, 2, 8, 0, 0, 0, 0, 0, 4, 0, 0, 7, 0, 0, 0, 13, 17,
2, 0, 1, 10, 16, 19, 6, 0, 0, 22, 18, 0, 25, 0, 0, 17, 21, 0, 13, 0, 0, 0, 14, 0, 0,
3, 0, 0, 0, 24, 0, 5, 14, 0, 15, 0, 11, 4, 23, 0, 0, 0, 0, 7, 0, 25, 16, 0, 0, 0,
0, 0, 0, 15, 0, 0, 0, 1, 18, 0, 13, 0, 9, 0, 10, 0, 22, 24, 0, 0, 7, 21, 0, 20, 8,
0, 0, 0, 19, 0, 0, 12, 20, 9, 25, 0, 24, 0, 14, 0, 6, 0, 0, 5, 16, 11, 4, 15, 18, 13,
0, 13, 0, 18, 23, 24, 21, 0, 2, 7, 5, 22, 0, 16, 0, 0, 0, 0, 0, 12, 17, 0, 9, 0, 0,
0, 0, 0, 22, 0, 5, 17, 25, 0, 0, 0, 0, 0, 21, 11, 1, 20, 0, 0, 0, 0, 10, 23, 0, 4,
24, 0, 6, 0, 0, 0, 18, 0, 4, 0, 7, 14, 0, 19, 0, 0, 8, 23, 16, 0, 13, 0, 0, 0, 5,
10, 16, 15, 0, 0, 2, 7, 8, 22, 0, 0, 0, 0, 17, 5, 9, 18, 0, 19, 0, 1, 0, 3, 0, 0,
20, 23, 0, 0, 12, 21, 0, 9, 0, 14, 2, 0, 0, 0, 22, 0, 13, 3, 11, 6, 0, 0, 0, 7, 0,
11, 0, 21, 25, 19, 10, 0, 0, 23, 0, 0, 0, 0, 20, 24, 0, 0, 17, 0, 15, 0, 0, 8, 2, 6,
8, 9, 22, 0, 0, 11, 19, 15, 24, 20, 17, 16, 0, 0, 13, 18, 0, 10, 21, 0, 0, 0, 4, 0, 0,
0, 12, 0, 1, 20, 25, 0, 18, 10, 0, 23, 7, 0, 0, 3, 0, 5, 9, 14, 4, 0, 0, 0, 0, 0,
0, 17, 25, 0, 0, 0, 0, 0, 0, 0, 0, 5, 1, 8, 4, 0, 12, 7, 0, 13, 16, 11, 0, 0, 24,
16, 0, 0, 21, 0, 0, 0, 0, 13, 0, 0, 15, 22, 0, 6, 3, 19, 25, 23, 0, 5, 0, 7, 8, 2,
0, 6, 0, 0, 10, 0, 22, 0, 0, 3, 0, 0, 0, 25, 2, 0, 0, 0, 15, 0, 21, 19, 0, 12, 0,
9, 0, 16, 13, 14, 1, 25, 0, 0, 0, 12, 8, 0, 15, 0, 7, 0, 0, 2, 22, 0, 0, 17, 3, 19,
0, 1, 10, 0, 0, 0, 9, 16, 7, 19, 0, 0, 24, 0, 14, 20, 0, 15, 0, 17, 0, 0, 5, 0, 0,
17, 22, 7, 0, 2, 0, 20, 4, 0, 12, 0, 19, 0, 0, 21, 25, 14, 6, 1, 8, 0, 0, 0, 23, 0,
23, 0, 5, 0, 0, 15, 0, 11, 21, 0, 0, 25, 0, 4, 0, 0, 0, 0, 0, 24, 14, 22, 6, 10, 0,
0, 0, 3, 0, 25, 0, 0, 0, 5, 13, 0, 17, 0, 0, 23, 0, 0, 0, 0, 19, 12, 7, 18, 0, 1 */
};
printf("before\n");
print_board(board);
if(solve(board)){
printf("after\n");
print_board(board);
}else{
printf("no answer exists");
}
return 0;
}
bool solve(int *board){
int i,j,cnt;
bool changed;
bool cand[CAND_SIZE+1];
do{
changed=FALSE;
for(i=0;i<ROW_SIZE*COL_SIZE;i++){
if(board[i]!=ND) continue;
get_cand(cand,board,i);
cnt=0;
for(j=1;j<=CAND_SIZE;j++){
if(cand[j]) cnt++;
}
if(cnt==CAND_SIZE-1){
for(j=1;j<=CAND_SIZE;j++){
if(!cand[j]){
board[i]=j;
changed=TRUE;
break;
}
}
}
}
}while(changed);
printf("intermediate\n");
print_board(board);
return dfs(board,0);
}
bool dfs(int *board,int depth){
int i;
bool cand[CAND_SIZE+1];
if(depth>=ROW_SIZE*COL_SIZE) return TRUE;
if(board[depth]!=ND) return dfs(board,depth+1);
get_cand(cand,board,depth);
for(i=1;i<=CAND_SIZE;i++){
if(cand[i]) continue;
board[depth]=i;
if(dfs(board,depth+1)) return TRUE;
}
board[depth]=ND;
return FALSE;
}
void get_cand(bool *cand,int *board,int pos){
int i,j;
int x=pos%(ROW_SIZE);
int y=pos/(ROW_SIZE);
for(i=1;i<=CAND_SIZE;i++){
cand[i]=FALSE;
}
for(i=0;i<COL_SIZE;i++){
cand[board[i*ROW_SIZE+x]]=TRUE;
}
for(i=0;i<ROW_SIZE;i++){
cand[board[y*ROW_SIZE+i]]=TRUE;
}
for(i=(y/SIZE)*SIZE;i<((y/SIZE)+1)*SIZE;i++){
for(j=(x/SIZE)*SIZE;j<((x/SIZE)+1)*SIZE;j++){
cand[board[i*ROW_SIZE+j]]=TRUE;
}
}
}
void print_board(int *board){
int i;
for(i=0;i<ROW_SIZE*COL_SIZE;i++){
printf("%2d ",board[i]);
if(i!=0 && i%(ROW_SIZE)==ROW_SIZE-1) printf("\n");
}
}