add c implementation of dlx sudoku

2 files changed, 198 insertions, 0 deletions

diff --git a/95-99/sudoku.c b/95-99/sudoku.c
new file mode 100644
index 0000000..f8591f7
--- /dev/null
+++ b/95-99/sudoku.c
@@ -0,0 +1,189 @@
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#define SUDOKU_N 3
+#define BLOCK_N (SUDOKU_N * SUDOKU_N)
+#define DIGITS_N BLOCK_N
+#define PLACE_BIT_N (BLOCK_N * BLOCK_N)
+#define BLOCK_BIT_N (BLOCK_N * DIGITS_N)
+#define ROW_BIT_N  BLOCK_BIT_N
+#define COL_BIT_N ROW_BIT_N
+#define SET_COVER_ROW (BLOCK_N * BLOCK_N * DIGITS_N)
+#define SET_COVER_COL (PLACE_BIT_N + BLOCK_BIT_N + ROW_BIT_N + COL_BIT_N)
+
+typedef struct DNode {
+    struct DNode *left, *right, *up, *down;
+    struct DNode *ctl;
+    uint32_t size, row;
+} DNode; /* the node of dlx */
+
+int bitmap[SET_COVER_ROW][SET_COVER_COL];
+int row_seq[SET_COVER_ROW];
+
+int puzzle[BLOCK_N][BLOCK_N];
+int backref[SET_COVER_ROW][3];
+
+DNode *dnode_new() {
+    return (DNode *)malloc(sizeof(DNode));
+}
+
+void dnode_free(DNode *p) {
+    free(p);
+}
+
+DNode *build_dlx(int nrow, int ncol) {
+    DNode *head = dnode_new();
+    DNode *chead[SET_COVER_COL];
+    head->left = head->right = head;
+    head->up = head->down = head;
+    int i, j;
+    /* build the guard chain */
+    for (j = 0; j < ncol; j++)
+    {
+        DNode *p = chead[j] = dnode_new();
+        (p->left = head->left)->right = p;
+        (p->right = head)->left = p;
+        p->up = p->down = p;
+    }
+    DNode *rhead = dnode_new(); /* helper node */
+    for (i = 0; i < nrow; i++)
+    {
+        rhead->left = rhead->right = rhead;
+        for (j = 0; j < ncol; j++)
+            if (bitmap[i][j])
+            {
+                DNode *p = dnode_new();
+                p->ctl = chead[j];
+                p->row = i;
+                (p->left = rhead->left)->right = p;
+                (p->right = rhead)->left = p;
+                (p->up = p->ctl->up)->down = p;
+                (p->down = p->ctl)->up = p;
+            }
+        rhead->left->right = rhead->right;
+        rhead->right->left = rhead->left;
+    }
+    dnode_free(rhead);
+    return head;
+}
+
+#define LOOP(q, p, d) for (q = p->d; q != p; q = q->d)
+
+void set_cover(DNode *pctl) {
+    DNode *q, *r;
+    pctl->left->right = pctl->right;
+    pctl->right->left = pctl->left;
+    LOOP(q, pctl, down)
+        LOOP(r, q, right)
+        {
+            r->up->down = r->down;
+            r->down->up = r->up;
+            r->ctl->size--;
+        }
+}
+
+void set_uncover(DNode *pctl) {
+    DNode *q, *r;
+    pctl->left->right = pctl;
+    pctl->right->left = pctl;
+    LOOP(q, pctl, up)
+        LOOP(r, q, left)
+        {
+            r->up->down = r;
+            r->down->up = r;
+            r->ctl->size++;
+        }
+}
+
+void dlx_print(int step) {
+    int i;
+    for (i = 0; i < step; i++)
+        printf("%d ", row_seq[i]);
+    puts("");
+}
+
+void sudoku_print(int step) {
+    int i, j;
+    for (i = 0; i < step; i++)
+    {
+        int *t = backref[row_seq[i]];
+        puzzle[t[0]][t[1]] = t[2];
+    }
+    for (i = 0; i < BLOCK_N; i++, puts(""))
+        for (j = 0; j < BLOCK_N; j++)
+            printf("%d ", puzzle[i][j]);
+    puts("");
+}
+
+void search(DNode *head, int step) {
+    DNode *p, *q, *lp;
+    uint32_t least_value = -1U;
+    if (head->left == head)
+    {
+        sudoku_print(step);
+        /* dlx_print(step); */
+        return;
+    }
+    LOOP(p, head, right)
+        if (p->size < least_value)
+        {
+            least_value = p->size;
+            lp = p;
+        }
+
+    set_cover(lp);
+    LOOP(p, lp, down)
+    {
+        LOOP(q, p, right) set_cover(q->ctl);
+        row_seq[step] = q->row;
+        search(head, step + 1);
+        LOOP(q, p, left) set_uncover(q->ctl);
+    }
+    set_uncover(lp);
+}
+
+void test_dlx() {
+    int nrow, ncol, i, j;
+    DNode *head;
+    scanf("%d %d", &nrow, &ncol);
+    for (i = 0; i < nrow; i++)
+        for (j = 0; j < ncol; j++)
+            scanf("%d", bitmap[i] + j);
+    head = build_dlx(nrow, ncol);
+    search(head, 0);
+}
+
+void sudoku() {
+    int i, j, d, nrow = 0;
+    DNode *head;
+    for (i = 0; i < BLOCK_N; i++)
+        for (j = 0; j < BLOCK_N; j++)
+            scanf("%d", puzzle[i] + j);
+    for (i = 0; i < BLOCK_N; i++)
+        for (j = 0; j < BLOCK_N; j++)
+            for (d = 0; d < DIGITS_N; d++)
+                if (!puzzle[i][j] || puzzle[i][j] == d + 1)
+                {
+                    int *b = bitmap[nrow];
+                    b[i * BLOCK_N + j] = 1;
+                    b += PLACE_BIT_N;
+                    b[((i / SUDOKU_N) * SUDOKU_N + j / SUDOKU_N) * BLOCK_N + d] = 1;
+                    b += BLOCK_BIT_N;
+                    b[i * BLOCK_N + d] = 1;
+                    b += ROW_BIT_N;
+                    b[j * BLOCK_N + d] = 1;
+                    backref[nrow][0] = i;
+                    backref[nrow][1] = j;
+                    backref[nrow][2] = d + 1;
+                    nrow++;
+                }
+    head = build_dlx(nrow, SET_COVER_COL);
+    search(head, 0);
+}
+
+int main() {
+    /* test_dlx(); */
+    sudoku();
+    return 0;
+}
diff --git a/95-99/sudoku.in b/95-99/sudoku.in
new file mode 100644
index 0000000..5d1d4de
--- /dev/null
+++ b/95-99/sudoku.in
@@ -0,0 +1,9 @@
+0 0 4 8 0 0 0 1 7
+6 7 0 9 0 0 0 0 0
+5 0 8 0 3 0 0 0 4
+3 0 0 7 4 0 1 0 0
+0 6 9 0 0 0 7 8 0
+0 0 1 0 6 9 0 0 5
+1 0 0 0 8 0 3 0 6
+0 0 0 0 0 6 0 9 1
+2 4 0 0 0 1 5 0 0