#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define BLOCK_SIZE 3
#define FIELD_WIDTH (BLOCK_SIZE*BLOCK_SIZE)
#define BITOFF(dest, bit) ((dest)^=(dest)&(1<<((bit)-1)))
typedef struct tag_sudoku_t
{
int data[FIELD_WIDTH][FIELD_WIDTH];
unsigned long flag[FIELD_WIDTH][FIELD_WIDTH];
}sudoku_t;
sudoku_t *sudoku_alloc(void)
{
sudoku_t *sudoku;
int x, y;
sudoku=malloc(sizeof(*sudoku));
for(y=0;y<FIELD_WIDTH;y++)
{
for(x=0;x<FIELD_WIDTH;x++)
{
sudoku->data[y][x]=0;
sudoku->flag[y][x]=(1<<FIELD_WIDTH)-1;
}
}
return sudoku;
}
int sudoku_number_set(sudoku_t *sudoku, int x, int y, int value)
{
int i, xx, yy;
if(value==0 || sudoku->data[y][x]!=0) return 0;
if(((sudoku->flag[y][x]>>(value-1))&1)==0) return 0;
// printf("(%2d,%2d) %2d->%2d\n", x, y, sudoku->data[y][x], value);
sudoku->data[y][x]=value;
for(i=0;i<FIELD_WIDTH;i++)
{
BITOFF(sudoku->flag[y][i], value);
BITOFF(sudoku->flag[i][x], value);
}
for(yy=y/BLOCK_SIZE*BLOCK_SIZE;yy<y/BLOCK_SIZE*BLOCK_SIZE+BLOCK_SIZE;yy++)
{
for(xx=x/BLOCK_SIZE*BLOCK_SIZE;xx<x/BLOCK_SIZE*BLOCK_SIZE+BLOCK_SIZE;xx++)
{
BITOFF(sudoku->flag[yy][xx], value);
}
}
return 1;
}
sudoku_t *sudoku_read(const char *filename)
{
sudoku_t *sudoku;
char buf[256], temp[3]="";
FILE *fp;
int x, y, value;
fp=fopen(filename, "r");
if(fp==NULL) return NULL;
sudoku=sudoku_alloc();
for(y=0;y<FIELD_WIDTH;y++)
{
fgets(buf, sizeof(buf), fp);
for(x=0;x<FIELD_WIDTH;x++)
{
temp[0]=buf[x*2];
temp[1]=buf[x*2+1];
if(sscanf(temp, "%d", &value)==1)
{
if(sudoku_number_set(sudoku, x, y, value)!=1)
{
exit(1);
}
}
}
}
fclose(fp);
return sudoku;
}
void sudoku_free(sudoku_t *sudoku)
{
free(sudoku);
}
int sudoku_copy(sudoku_t *dest, const sudoku_t *src)
{
if(dest==NULL || src==NULL) return 0;
memcpy(dest, src, sizeof(*src));
return 1;
}
sudoku_t *sudoku_dup(const sudoku_t *sudoku)
{
sudoku_t *copy;
copy=sudoku_alloc();
sudoku_copy(copy, sudoku);
return copy;
}
void sudoku_print(sudoku_t *sudoku)
{
int x, y;
if(sudoku==NULL) return;
for(y=0;y<FIELD_WIDTH;y++)
{
if(y%BLOCK_SIZE==0) printf("\n");
for(x=0;x<FIELD_WIDTH;x++)
{
if(x%BLOCK_SIZE==0 && x!=0) printf(" ");
if(sudoku->data[y][x]) printf(" %02d", sudoku->data[y][x]);
else printf(" ■");
}
printf("\n");
}
/*
for(y=0;y<FIELD_WIDTH;y++)
{
for(x=0;x<FIELD_WIDTH;x++)
{
printf(" %07lX", sudoku->flag[y][x]);
}
printf("\n");
}
*/
}
int bitcount(unsigned long value)
{
int count=0;
for(;value;value>>=1)
{
count+=(value&1);
}
return count;
}
int lowestbit(unsigned long value)
{
int i;
for(i=1;value;i++,value>>=1)
{
if(value&1) break;
}
return i;
}
void solve_fix_number(sudoku_t *sudoku)
{
int is_changed, x, y;
unsigned long flag;
do
{
is_changed=0;
// sudoku_print(sudoku);
for(y=0;y<FIELD_WIDTH;y++)
{
for(x=0;x<FIELD_WIDTH;x++)
{
flag=sudoku->flag[y][x];
if(bitcount(flag)==1)
{
if(sudoku_number_set(sudoku, x, y, lowestbit(flag)))
{
is_changed=1;
}
}
}
}
}
while(is_changed);
}
int solve(sudoku_t *sudoku)
{
sudoku_t *work;
int i, x, y, is_finished=1, min_x, min_y, min_bit=FIELD_WIDTH, bit;
work=sudoku_alloc();
solve_fix_number(sudoku);
for(y=0;y<FIELD_WIDTH;y++)
{
for(x=0;x<FIELD_WIDTH;x++)
{
if(sudoku->data[y][x]!=0) continue;
bit=bitcount(sudoku->flag[y][x]);
if(bit==0)
{
// printf("error\n");
return 0;
}
if(bit<min_bit)
{
min_x=x;
min_y=y;
min_bit=bit;
}
is_finished=0;
}
}
if(!is_finished)
{
for(i=0;i<FIELD_WIDTH;i++)
{
if((sudoku->flag[min_y][min_x]>>i)&1)
{
sudoku_copy(work, sudoku);
// printf("try (%2d,%2d) -> %d\n", min_x, min_y, i+1);
sudoku_number_set(work, min_x, min_y, i+1);
solve(work);
}
}
}
if(is_finished) sudoku_print(sudoku);
sudoku_free(work);
return 1;
}
int main(int argc, char *argv[])
{
char *filename="sudoku25.txt";
int i, q[]={
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
};
sudoku_t *sudoku;
// sudoku=sudoku_read(filename);
sudoku=sudoku_alloc();
for(i=0;i<FIELD_WIDTH*FIELD_WIDTH;i++) if(q[i]) sudoku_number_set(sudoku, i%FIELD_WIDTH, i/FIELD_WIDTH, q[i]);
solve(sudoku);
sudoku_free(sudoku);
return 0;
}