sudoku solver

sudoku.c

#include <stdint.h>
#include <stdio.h> /* fprintf, getchar, printf, putchar, stderr */
#include <stdlib.h> /* exit, free, malloc */
#include <string.h> /* memmove */

#define N 9
#define mask ((1<<N) - 1)
typedef uint16_t Cell;

Cell puz[N*N];

void readpuz(void);
void printpuz(void);
int  check(void);
void solve(void);
int  reduce(void);
int  promote(void);
int  guess(void);

Cell* save(void);
void  reset(Cell*);
int nsave;
int nreset;

char* cellstr(Cell c);

int debug;

Cell get(int i, int j)  { return puz[i*N + j]; }
void set(int i, int j, Cell c) {
	if (debug) {
		printpuz();
		printf("puz[%d][%d]: ", i, j);
		printf("%s => ", cellstr(get(i, j)));
		printf("%s\n", cellstr(c));
	}
	puz[i*N + j] = c;
}

Cell getbox(int i, int j)  { return get(i/3*3 + j/3, i%3*3 + j%3); }
void setbox(int i, int j, Cell c) { set(i/3*3 + j/3, i%3*3 + j%3, c); }

Cell geta(int a, int i, int j) {
	switch (a) {
	case 0: return get(i, j);
	case 1: return get(j, i);
	case 2: return getbox(i, j);
	}
	return 0;
}

void seta(int a, int i, int j, Cell c) {
	switch (a) {
	case 0: set(i, j, c); break;
	case 1: set(j, i, c); break;
	case 2: setbox(i, j, c); break;
	}
}

// reports which square the cell at i,j belongs to
int boxof(int i, int j) { return i/3*3 + j/3; }

int known(Cell c) {
	return c && (c & (c-1)) == 0;
}

int len(Cell c) {
	int n = 0;
	while (c) {
		c &= c - 1;
		n++;
	}
	return n;
}

int num(Cell c) {
	int n = 0;
	if (known(c)) {
		while (c) {
			c >>= 1;
			n++;
		}
	}
	return n;
}

/*
int len(Cell c) {
	return __builtin_popcount(c);
}

int num(Cell c) {
	if (known(c)) {
		return __builtin_ffs(c);
	}
	return 0;
}
*/

char* cellstr(Cell c) {
	static char buf[3*N + 10];
	int n, i = 0;
	buf[i++] = '{';
	for (n = 0; n < N; n++) {
		if (c&1) {
			if (i > 1) {
				buf[i++] = ',';
				buf[i++] = ' ';
			}
			buf[i++] = '1' + n;
		}
		c >>= 1;
	}
	buf[i++] = '}';
	buf[i++] = '\0';
	return buf;
}

void readpuz(void) {
	int c, i;
	for (i = 0; i < N*N;) {
		c = getchar();
		if (c == EOF) {
			fprintf(stderr, "unexpected EOF\n");
			exit(2);
		}
		else if ('1' <= c && c <= '9') {
			puz[i] = 1U<<(c - '1');
			i++;
		}
		else if (c == '.') {
			puz[i] = mask;
			i++;
		}
	}
}

void printpuz(void) {
	int i, j;
	Cell c;

	for (i = 0; i < N; i++)
	for (j = 0; j < N; j++) {
		c = get(i, j);

		if (c == 0) {
			putchar('?');
		} else if (known(c)) {
			putchar('0' + num(c));
		} else {
			putchar('.');
		}

		if (j < N-1) {
			putchar(' ');
		} else {
			putchar('\n');
		}
	}
}

// check the puzzle
//
// 0: not solved
// 1: solved
// 2: invalid
//
int check(void) {
	int i, j, k;
	Cell c, m;

	Cell row[N];
	Cell col[N];
	Cell box[N];

	Cell rowm[N];
	Cell colm[N];
	Cell boxm[N];

	for (i = 0; i < N; i++) {
		row[i] = 0;
		col[i] = 0;
		box[i] = 0;

		rowm[i] = 0;
		colm[i] = 0;
		boxm[i] = 0;
	}

	for (i = 0; i < N; i++)
	for (j = 0; j < N; j++) {
		c = get(i, j);
		k = boxof(i, j);

		row[i] |= c;
		col[j] |= c;
		box[k] |= c;

		if (known(c)) {
			if (rowm[i] & c || colm[j] & c || boxm[k] & c) {
				return 2;
			}
			rowm[i] |= c;
			colm[j] |= c;
			boxm[k] |= c;
		}
	}

	m = mask;
	for (i = 0; i < N; i++) {
		if (row[i] != mask ||
				col[i] != mask ||
				box[i] != mask) {
			return 2;
		}
		m &= rowm[i] & colm[i] & boxm[i];
	}
	if (m == mask) {
		return 1;
	}
	return 0;
}

void solve(void) {
	while (!check()) {
		if (reduce()) {
			continue;
		}
		if (promote()) {
			continue;
		}
		if (guess()) {
			return;
		}
		break;
	}
}

// Propagate known cells out to reduce the possibilities in other cells.
int reduce(void) {
	int i, j, ret;
	Cell c, m;

	Cell row[N];
	Cell col[N];
	Cell box[N];

	for (i = 0; i < N; i++) {
		row[i] = 0;
		col[i] = 0;
		box[i] = 0;
	}

	for (i = 0; i < N; i++)
	for (j = 0; j < N; j++) {
		c = get(i, j);
		if (known(c)) {
			row[i] |= c;
			col[j] |= c;
			box[boxof(i, j)] |= c;
		}
	}

	ret = 0;
	for (i = 0; i < N; i++)
	for (j = 0; j < N; j++) {
		c = get(i, j);
		if (!known(c)) {
			m = ~(row[i] | col[j] | box[boxof(i, j)]);
			if (c != (c&m)) {
				set(i, j, c&m);
				ret++;
			}
		}
	}
	return ret;
}

// if a cell is the only choice for a number, it must be that number
int promote(void) {
	int a, i, j, n, ret;
	Cell c, m, row[N];

	ret = 0;
	for (a = 0; a < 3; a++)
	for (i = 0; i < N; i++) {
		for (n = 0; n < N; n++) {
			row[n] = 0;
		}

		for (j = 0; j < N; j++) {
			c = geta(a, i, j);
			for (n = 0; c; n++) {
				if (c&1) {
					row[n] |= 1U<<j;
				}
				c >>= 1;
			}
		}

		for (n = 0; n < N; n++) {
			if (known(row[n])) {
				j = num(row[n])-1;
				m = 1U<<n;
				if (geta(a, i, j) != m) {
					seta(a, i, j, m);
					ret++;
				}
			}
		}
	}

	return ret;
}

Cell *save(void) {
	Cell *copy;
	copy = malloc(sizeof puz);
	if (copy == NULL) {
		fprintf(stderr, "out of memory\n");
		exit(2);
	}
	nsave++;
	memmove(copy, puz, sizeof puz);
	return copy;
}

void reset(Cell *copy) {
	nreset++;
	memmove(puz, copy, sizeof puz);
}

int guess(void) {
	Cell c, m, *oldpuz;
	int i, j, n;

	for (n = 2; n <= N; n++)
	for (i = 0; i < N; i++)
	for (j = 0; j < N; j++) {
		c = get(i, j);
		if (len(c) == n) {
			goto found;
		}
	}
	return 0;

found:
	oldpuz = save();
	for (n = 0; n < N; n++) {
		m = 1U<<n;
		if (c & m) {
			set(i, j, m);
			solve();
			if (check() == 1) {
				free(oldpuz);
				return 1;
			}
			reset(oldpuz);
		}
	}
	free(oldpuz);
	return 0;
}

char* plural(int n, char* singular, char* plural) {
	if (n == 1) {
		return singular;
	}
	return plural;
}

int main() {
	readpuz();
	//printpuz();
	//putchar('\n');
	solve();
	//printf("%d\n", check());
	printpuz();
	printf("split %d %s\n", nsave, plural(nsave, "time", "times"));
	printf("failed %d %s\n", nreset, plural(nreset, "time", "times"));
	exit(check());
}