commit eab5b7383124afd2f84ee52cb53b4324730a3266
parent 9024f9695a499277fd274b713a26bad1994ee2d9
Author: Henry Wilson <henry@henryandlizzy.uk>
Date: Mon, 16 May 2022 23:29:16 +0100
Add sudoku example
Diffstat:
| A | src/sudoku.c | | | 227 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 227 insertions(+), 0 deletions(-)
diff --git a/src/sudoku.c b/src/sudoku.c
@@ -0,0 +1,227 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <ctype.h>
+#include <assert.h>
+#include <unistd.h>
+
+#define ORDER 3
+#define WIDTH (ORDER*ORDER)
+#define CELLS (WIDTH*WIDTH)
+
+struct grid
+{
+ unsigned short cells[CELLS];
+ unsigned char assigned;
+};
+
+static unsigned count_ones(unsigned x)
+{
+ unsigned n = 0;
+ while (x)
+ {
+ n += x & 1;
+ x >>= 1;
+ }
+ return n;
+}
+
+static unsigned unshift(unsigned x)
+{
+ unsigned n = 0;
+ assert(count_ones(x) == 1);
+
+ while (~x & 1)
+ {
+ x >>= 1;
+ ++n;
+ }
+ return n;
+}
+
+static int is_mod_max(unsigned x, unsigned mod)
+{
+ return x % mod == mod - 1;
+}
+
+static void print_grid(struct grid const* g)
+{
+ char buf[2 * CELLS];
+ char* b = buf;
+
+ for (unsigned i = 0; i < CELLS; ++i)
+ {
+ unsigned cell = g->cells[i];
+ unsigned ones = count_ones(cell);
+
+ if (!cell)
+ *b++ = '!';
+ else if (ones > 1)
+ *b++ = ' ';
+ else
+ *b++ = '1' + unshift(cell);
+
+ if (is_mod_max(i, WIDTH))
+ {
+ *b++ = '\n';
+ if (is_mod_max(i, WIDTH * ORDER))
+ *b++ = '\n';
+ }
+ else if (is_mod_max(i, ORDER))
+ *b++ = ' ';
+ }
+ assert(write(1, buf, b - buf) == b - buf);
+}
+
+static unsigned pick_one(unsigned choices)
+{
+ unsigned n = 0;
+ unsigned val = 1;
+ do
+ {
+ while (val & ~choices)
+ val <<= 1;
+ } while (n--);
+
+ assert(val);
+ return val;
+}
+
+static unsigned round_down(unsigned n, unsigned radix)
+{
+ return n / radix * radix;
+}
+
+static int resolve_assignment(struct grid* g, unsigned c);
+
+static int exclude(struct grid* g, unsigned cell, unsigned val)
+{
+ unsigned short* c = g->cells + cell;
+ if (*c == val)
+ return 0;
+ if (~*c & val)
+ return 1;
+
+ *c &= ~val;
+
+ if (count_ones(*c) == 1)
+ return resolve_assignment(g, cell);
+ return 1;
+}
+
+static int resolve_assignment(struct grid* g, unsigned c)
+{
+ unsigned val = g->cells[c];
+ g->assigned++;
+
+ for (unsigned x = 0; x < WIDTH; ++x)
+ {
+ unsigned C = round_down(c, WIDTH) + x;
+ if (C != c)
+ if (!exclude(g, C, val))
+ return 0;
+ }
+
+ for (unsigned y = 0; y < WIDTH; ++y)
+ {
+ unsigned C = (c % WIDTH) + WIDTH * y;
+ if (C != c)
+ if (!exclude(g, C, val))
+ return 0;
+ }
+
+ for (unsigned z = 0; z < WIDTH; ++z)
+ {
+ unsigned C = round_down(c, WIDTH * ORDER) + c / ORDER % ORDER * ORDER;
+ C += z / ORDER * WIDTH;
+ C += z % ORDER;
+ if (C != c)
+ if (!exclude(g, C, val))
+ return 0;
+ }
+
+ return 1;
+}
+
+static int try_grid(struct grid g)
+{
+ if (g.assigned == CELLS)
+ {
+ print_grid(&g);
+ return 1;
+ }
+
+ unsigned x = 0;
+ unsigned c = 0;
+ do
+ {
+ while (count_ones(g.cells[c]) == 1)
+ ++c;
+ ++c;
+ } while (x--);
+ --c;
+ unsigned val = pick_one(g.cells[c]);
+
+ struct grid G = g;
+ G.cells[c] = val;
+ if (resolve_assignment(&G, c))
+ if (try_grid(G))
+ return 1;
+
+ G = g;
+ G.cells[c] &= ~val;
+ if (count_ones(G.cells[c]) == 1)
+ if (!resolve_assignment(&G, c))
+ return 0;
+
+ return try_grid(G);
+}
+
+void init_grid(struct grid* g, char const* str)
+{
+ for (unsigned i = 0; *str && i < CELLS; ++str)
+ {
+ if (*str == '\n')
+ {
+ i = round_down(i + WIDTH, WIDTH);
+ continue;
+ }
+ while (isspace(*str))
+ if(!*++str)
+ return;
+
+ if (isdigit(*str) && *str != '0')
+ {
+ g->cells[i] = 1 << (*str - '1');
+ g->assigned++;
+ }
+ ++i;
+ }
+}
+
+char const test[] =
+"53..7...."
+"6..195..."
+".98....6."
+"8...6...3"
+"4..8.3..1"
+"7...2...6"
+".6....28."
+"...419..5"
+"....8..79";
+
+int main()
+{
+ struct grid g;
+
+ unsigned mask = 0;
+ for (unsigned i = 0; i < WIDTH; ++i)
+ mask |= 1 << i;
+ for (unsigned i = 0; i < CELLS; ++i)
+ g.cells[i] = mask;
+
+ init_grid(&g, test);
+// print_grid(&g);
+
+
+ return !try_grid(g);
+}
