Sudoku solver

example.txt

53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79

Makefile

.PHONY: test
test: seppuku
	./seppuku < example.txt

seppuku: seppuku.c
	gcc -std=c99 -o $@ $<

seppuku.c

#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BLANKCELL ((1 << 9) - 1)

struct frame {
	uint16_t soln[9][9];
	uint16_t filter[9][9];
};

int
is_possible(uint16_t x, int n)
{
	return !!(x & (1 << (n - 1)));
}

int is_fixed(uint16_t x)
{
	if (!x)
		return 1;
	while (!(x & 1))
		x >>= 1;
	return x == 1;
}

char
filtoc(uint16_t x)
{
	int n;
	for (n = 0; x; ++n)
		x >>= 1;
	return n ? '0' + n: ' ';
}

void
pretty_print_frame(struct frame *s)
{
	char bord[] = "-------------------";
	char line[] = "| ??? | ??? | ??? |";
	int k;
	printf("%s\n", bord);
	for (int i = 0; i < 9; ++i) {
		for (int j = 0; j < 9; ++j) {
			k = j < 3 ? j + 2 : j < 6 ? j + 5 : j + 8;
			line[k] = filtoc(s->soln[i][j]);
		}
		printf("%s\n", line);
		if (i % 3 == 2)
			printf("%s\n", bord);
	}
}

int
remaining(struct frame *s)
{
	int n = 0;
	for (int i = 0; i < 81; ++i) {
		if (!s->soln[0][i])
			n++;
	}
	return n;
}

uint16_t sum_col_around(uint16_t (*cells)[9][9], int i, int b)
{
	uint16_t sum = 0;
	for (int j = 0; j < 9; ++j)
		if (j != b)
			sum |= (*cells)[i][j];
	return sum;
}

uint16_t sum_row_around(uint16_t (*cells)[9][9], int a, int j)
{
	uint16_t sum = 0;
	for (int i = 0; i < 9; ++i)
		if (i != a)
			sum |= (*cells)[i][j];
	return sum;
}

uint16_t sum_sec_around(uint16_t (*cells)[9][9], int a, int b)
{
	uint16_t sum = 0;
	for (int i = 3 * (a / 3); i < 3 * (a / 3 + 1); ++i)
		for (int j = 3 * (b / 3); j < 3 * (b / 3 + 1); ++j)
			if (i != a || j != b)
				sum |= (*cells)[i][j];
	return sum;
}

void
solve(struct frame *s)
{
	memcpy(&s->filter, &s->soln, sizeof(s->filter));
	uint16_t x;
	int modified = 1;
	while (modified > 0) {
		modified = 0;
		for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j) {
				if (s->soln[i][j])
					continue;
				s->filter[i][j] = 0;
				s->filter[i][j] |= sum_col_around(&s->soln, i, j);
				s->filter[i][j] |= sum_row_around(&s->soln, i, j);
				s->filter[i][j] |= sum_sec_around(&s->soln, i, j);
				s->filter[i][j] = BLANKCELL ^ s->filter[i][j];
				if (!s->filter[i][j]) {
					fprintf(stderr, "Inconsistent: no possible value for cell\n");
				}
				if (is_fixed(s->filter[i][j])) {
					modified += s->soln[i][j] != s->filter[i][j];
					s->soln[i][j] = s->filter[i][j];
				}
			}
		}
		if (modified)
			continue;
		for (int i = 0; i < 9; ++i) {
			for (int j = 0; j < 9; ++j) {
				if (s->soln[i][j])
					continue;
				x = BLANKCELL ^ sum_col_around(&s->filter, i, j);
				if (x) {
					// There is a column that can't be solved elsewhere
					if (!is_fixed(x)) {
						fprintf(stderr, "Inconsistent: cell must have more than one value\n");
					}
					s->soln[i][j] = x;
					puts("Helped1");
					modified = 1;
				} else {
					x = BLANKCELL ^ sum_row_around(&s->filter, i, j);
					if (x) {
						if (!is_fixed(x)) {
							fprintf(stderr, "Inconsistent: cell must have more than one value\n");
						}
						s->soln[i][j] = x;
						puts("Helped2");
						modified = 1;
					} else {
						x = BLANKCELL ^ sum_sec_around(&s->filter, i, j);
						if (x) {
							if (!is_fixed(x)) {
								fprintf(stderr, "Inconsistent: cell must have more than one value\n");
							}
							s->soln[i][j] = x;
							puts("Helped3");
							modified = 1;
						}
					}
				}
			}
		}
	}
}

int
main(void)
{
	struct frame *s = calloc(1, sizeof(*s));
	int c;
	for (int i = 0; i < 9; ++i) {
		for (int j = 0; j < 9; ++j) {
			c = getchar();
			if ('1' <= c && c <= '9') {
				s->soln[i][j] = 1 << (c - '1');
			} else if (c != ' ' && c != '.') {
				fprintf(stderr, "Error on line %d\n", i + 1);
				exit(1);
			}
		}
		while (getchar() != '\n');
	}
	pretty_print_frame(s);
	printf("Remaining: %d\n", remaining(s));
	printf("\n");
	solve(s);
	pretty_print_frame(s);
	printf("Remaining: %d\n", remaining(s));
	printf("\n");
}

soln.txt

534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179