Sudoku.c

#include <stdio.h>

#define ROWS 9
#define COLS 9
#define SQ 3
#define MAX (SQ*SQ)

static void read_question(FILE *fp);
static int find_blank(int *, int *);
static int solve(int, int);
static int examine_blank(int, int, char *);
static void print_ans();

static int map[ROWS][COLS];

int main(int argc, char *argv[])
{
	read_question(stdin);
	solve(0, 0);
	return 0;
}

/* Find blank starting from (r,c) */
/* You can always start from (0, 0), this is for speed */
static int find_blank(int *r, int *c)
{

	int i = (*r)*COLS+*c;
	for(;i<ROWS*COLS; i++){
		if(!map[0][i]){
			*r = i/COLS;
			*c = i%COLS;
			return 1;
		}
	}
	return 0;
}

static int solve(int r, int c)
{
	int rnt=0;
	int k;
	/* impossible number */
	char im_number[MAX+1]={0};
	/* If there's no blank left, then this is the end, print the answer */
	if(!find_blank(&r, &c)) {
		print_ans();
		putchar('\n');
		return 1;
	}

	/* Examine possible number */
	examine_blank(r, c, im_number);

	for(k=1; k<=MAX; k++) {
		if(!im_number[k]) {
			map[r][c]=k;
			rnt+=solve(r, c);
			map[r][c]=0;
		}
	}
	return rnt;
}

static int examine_blank(int r, int c, char *res)
{
	int i;
	for(i=0; i<ROWS; i++)
		res[map[i][c]]=1;
	for(i=0; i<COLS; i++)
		res[map[r][i]]=1;
	/* locate upper-left corner of (r, c) */
	r=r/SQ*SQ;
	c=c/SQ*SQ;
	for(i=0; i<MAX; i++)
		res[map[r+i/SQ][c+i%SQ]]=1;
}

static void print_ans()
{
	int i, j;
	for(i=0; i<ROWS; i++) {
		for(j=0; j<COLS; j++)
			printf("%d ", map[i][j]);
		putchar('\n');
	}
}

static void read_question(FILE *fp)
{
	int i, j;
	for(i=0; i<ROWS; i++)
		for(j=0; j<COLS; j++)
			fscanf(fp, "%d", &map[i][j]);
}