sudokusolve.c

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <time.h>

#define NVALUE	9 // box contains no value

#define SECT(n) ((n / 3) * 3) // start of sector for index
#define NSECT(n) (SECT(n) + 3) // start of next sector for index

#define POSS(v) __builtin_popcount(v) // possible values in possibility n

unsigned int sudoku[9][9]; // sudoku

int solutioncount = 0; // number of solutions
int solutionprint = 0; // whether to print the solutions

void sudokuoutput() {
	const char delim[] = "###################";
	const char sep[] = "#-+-+-#-+-+-#-+-+-#";
	for (int y = 0; y < 9; y++) {
		if ((y % 3) == 0) {
			puts(delim);
		} else {
			puts(sep);
		}
		for (int x = 0; x < 9; x++) {
			if ((x % 3) == 0) {
				putchar('#');
			} else {
				putchar('|');
			}
			if (sudoku[x][y] == NVALUE) {
				putchar(' ');
			} else {
				putchar('1' + sudoku[x][y]);
			} 
		}
		puts("#");
	}
	puts(delim);
}

unsigned int updatep(int x, int y) {
	unsigned int vn = 0;
	for (int ix = 0; ix < 9; ix++) {
		vn |= 1 << sudoku[ix][y];
	}
	for (int iy = 0; iy < 9; iy++) {
		vn |= 1 << sudoku[x][iy];
	}
	for (int sx = SECT(x); sx < NSECT(x); sx++) {
		for (int sy = SECT(y); sy < NSECT(y); sy++) {
			vn |= 1 << sudoku[sx][sy];
		}
	}
	return 0x1ff & ~(vn);
}

void sudokusolve() {
	int mx = -1, my = -1, mc = 10;
	unsigned int mp = 0;
	
	// find the spot with the least amount of possibilities
	for (int x = 0; x < 9; x++) {
		for (int y = 0; y < 9; y++) {
			if (sudoku[x][y] != NVALUE) {
				continue;
			}
			unsigned int p = updatep(x, y);
			unsigned int n = POSS(p);
			if (n < mc) {
				mc = n;
				mx = x;
				my = y;
				mp = p;
			}
		}
	}
	
	// one of the box has no possible value!
	if (mc == 0) {
		return;
	}
	
	// all the values are set, it's a solution!
	if (mc == 10) {
		printf("Found solution %d\n", solutioncount++);
		if (solutionprint) {
			sudokuoutput();
			putchar('\n');
		}
		return;
	}
	
	// try solve with value
	for (unsigned int i = 0; i < 9; i++) {
		if (mp & (1 << i)) {
			sudoku[mx][my] = i;
			sudokusolve();
		}
	}
	
	// undo for other possible solutions
	sudoku[mx][my] = NVALUE;
}

int main(int argc, char *argv[]) {
	if (argc <  2) {
		puts("usage: sudokusolve [input] (-s)");
		puts("-s: output solutions");
		return 0;
	}
	
	if (argc == 3) {
		if (!strcmp(argv[2], "-s")) {
			solutionprint = 1;
		}
	}

	for (int x = 0; x < 9; x++) {
		for (int y = 0; y < 9; y++) {
			sudoku[x][y] = NVALUE;
		}
	}

	// input sudoku
	FILE *f = fopen(argv[1], "rw+");
	int ch, x = 0, y = 0;
	while ((ch = fgetc(f)) != EOF) {
		if (ch == '\n') {
			y = (y + 1) % 9;
			x = 0;
			continue;
		}
		if ((ch >= '1') && (ch <= '9')) {
			sudoku[x][y] = ch - '1';
		} else if (ch != ' ') {
			continue;
		}
		x = (x + 1) % 9;
	}
	fclose(f);
	
	puts("Input sudoku:");
	sudokuoutput(&sudoku);

	// solve sudoku
	puts("\n\nSolving...\n");
	clock_t t = clock();
	sudokusolve();
	t = clock() - t;
	printf("\n\nSolved in %f seconds\n", (double)t / CLOCKS_PER_SEC);
	printf("The sudoku has %d solutions\n", solutioncount);
}