Skip to content

Instantly share code, notes, and snippets.

@louisswarren

louisswarren/Makefile

Last active Jul 27, 2020
Embed
What would you like to do?
Sudoku solver
53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
.PHONY: test
test: seppuku
./seppuku < example.txt
seppuku: seppuku.c
gcc -std=c99 -o $@ $<
#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");
}
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.