A classical Dancing Links solver with Sudoku and N Queens setups

dlss.c

/* A classical Dancing Links solver with Sudoku and N Queens setups. */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <setjmp.h>

// Dancing links Algorithm X exactly from Knuth's paper.

typedef struct data {
  struct data *l, *r, *u, *d;
  struct column *c;
  int nRow;
} DATA;

typedef struct column {
  DATA data[1];
  int size;
  int nCol;
} COLUMN;

typedef struct solution {
  struct solution *prev;
  DATA *data;
} SOLUTION;

static void init(DATA *p, COLUMN *c, int nRow) {
  p->u = p->d = p->l = p->r = p;
  p->c = c;
  p->nRow = nRow;
}

static void pushLeft(DATA *p, DATA *r) {
  p->l = r->l;
  p->r = r;
  r->l = p;
  p->l->r = p;
}

static void pushAbove(DATA *p, DATA *b) {
  p->u = b->u;
  p->d = b;
  b->u = p;
  p->u->d = p;
}

static void insertHead(DATA *p, COLUMN *c, int nRow) {
  init(p, c, nRow);
  pushAbove(p, c->data);
  ++c->size;
}

static void insert(DATA *p, COLUMN *c, int nRow, DATA *r) {
  init(p, c, nRow);
  pushLeft(p, r);
  pushAbove(p, c->data);
  ++c->size;
}

static void initColumn(COLUMN *p, int nCol, COLUMN *r) {
  p->size = 0;
  p->nCol = nCol;
  init(p->data, p, -1);
  pushLeft(p->data, r->data);
}

static void cover(DATA *c) {
  c->r->l = c->l;
  c->l->r = c->r;
  for (DATA *i = c->d; i != c; i = i->d) {
    for (DATA *j = i->r; j != i; j = j->r) {
      j->d->u = j->u;
      j->u->d = j->d;
      --j->c->size;
    }
  }
}

static void uncover(DATA *c) {
  for (DATA *i = c->u; i != c; i = i->u) {
    for (DATA *j = i->l; j != i; j = j->l) {
      ++j->c->size;
      j->d->u = j;
      j->u->d = j;
    }
  }
  c->r->l = c;
  c->l->r = c;
}

static DATA *chooseNextColumn(DATA *h) {
  DATA *p_min = h->r;
  for (DATA *p = p_min->r; p != h; p = p -> r)
    if (p->c->size < p_min->c->size) p_min = p;
  return p_min;
}

// A C-ified closure for the function called to emit a solution.
typedef struct emitter {
  void (*emit)(SOLUTION*, struct emitter*);
} EMITTER;

static void search(DATA *h, SOLUTION *s, EMITTER *emitter) {
  if (h->r == h) {
    emitter->emit(s, emitter);
    return;
  }
  DATA *c = chooseNextColumn(h);
  cover(c);
  for (DATA *r = c->d; r != c; r = r->d) {
    for (DATA *j = r->r; j != r; j = j->r) cover(j->c->data);
    SOLUTION sNew[1] = {{ s, r }};
    search(h, sNew, emitter); 
    for (DATA *j = r->l; j != r; j = j->l) uncover(j->c->data);
    c = r->c->data;
  }
  uncover(c);
}

// Set up the general purpose Algorithm X constraint solver with an N-Queens problem.

// With this decl, C guarantees that casting EMITTER* to NQUEENS_EMITTER* does the right thing.
typedef struct nqueens_emitter {
  EMITTER emitter[1];
  int n;
} NQUEENS_EMITTER;

static void emitNQueensSoln(SOLUTION *s, EMITTER *e) {
  NQUEENS_EMITTER *nqe = (NQUEENS_EMITTER*) e;
  int n = nqe->n;
  char board[n][n];
  memset(board, '.', n * n * sizeof(char));
  while (s) {
    int ij = s->data->nRow; // nRow is encoded board row and column
    if (ij < nqe->n * nqe->n) board[ij / nqe->n][ij % nqe->n] = 'Q';
    s = s->prev;
  }
  for (int i = 0; i < n; ++i) printf("%.*s\n", n, board[i]);
  printf("\n");
}

// Column number encoders
#define R(I) (I)
#define C(J) ((J) + n)
#define NESW(I, J) (2 * n + (I) + (J) - 1)
#define NWSE(I, J) (5 * n + (I) - (J) - 5)
#define DIAG_LO NESW(0,1)
#define DIAG_HI (nCols - 1) // Same as NWSE(n - 2, 0)
// Index conditions.
#define N (i == 0)
#define S (i == n - 1)
#define W (j == 0)
#define E (j == n - 1)
#define CORNER(A, B) (A && B)

static void solveNQueens(int n) {
  // Set up the header.
  COLUMN h[1];
  init(h->data, h, -1);
  h->size = h->nCol = -1;

  // Set up columns.
  int nCols = 6 * n - 6; 
  COLUMN cols[nCols][1];
  for (int j = 0; j < nCols; ++j) initColumn(cols[j], j, h);
  
  // Set up the pool of data objects and an allocation pointer.
  int nData = (4 * n + 4) * n - 10;
  DATA data[nData][1];
  int dp = 0;
  // Build matrix.
  int nRow = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j, ++nRow) {
      DATA *head = data[dp++];
      insertHead(head, cols[R(i)], nRow);
      insert(data[dp++], cols[C(j)], nRow, head);
      if (!CORNER(N,W) && !CORNER(S,E)) insert(data[dp++], cols[NESW(i,j)], nRow, head);
      if (!CORNER(N,E) && !CORNER(S,W)) insert(data[dp++], cols[NWSE(i,j)], nRow, head);
    }
  }
  // Diagonal relaxation rows.
  for (int i = DIAG_LO; i <= DIAG_HI; ++i) insertHead(data[dp++], cols[i], nRow++);
  NQUEENS_EMITTER nqe[1] = {{{emitNQueensSoln}, n}};
  search(h->data, NULL, nqe->emitter);
}

int other_main(void) {
  solveNQueens(5);
  return 0;
}

// Set up the general purpose Algorithm X constraint solver with a Sudoku problem.

// Row and column number encoders.
#define S(X, Y) (((X) * 9) + (Y))
#define OFS(N) ((N) * 9 * 9)
#define RC(R, C) (S(R, C) + OFS(0))
#define RV(R, V) (S(R, V) + OFS(1))
#define CV(C, V) (S(C, V) + OFS(2))
#define BV(B, V) (S(B, V) + OFS(3))
#define BLK(I, J) (((I) / 3) * 3 + (J) / 3)

#define SIZE(A) (sizeof A / sizeof A[0])

// With this decl, C guarantees that casting EMITTER* to SUDOKU_EMITTER* does the right thing.
typedef struct sudoku_emitter {
  EMITTER emitter[1];
  char (*board)[9];
  jmp_buf done;
} SUDOKU_EMITTER;

static void emitSudokuSoln(SOLUTION *s, EMITTER *e) {
  SUDOKU_EMITTER *se = (SUDOKU_EMITTER*) e;
  while (s) {
    int rcv = s->data->nRow; // nRow is encoded Sudoku row, column, value
    se->board[rcv / 81][rcv / 9 % 9] = '1' + rcv % 9;
    s = s->prev;
  }
  longjmp(se->done, 1);
}

static void solveSudoku(char board[9][9]) {
  // Set up the header.
  COLUMN h[1];
  init(h->data, h, -1);
  h->size = h->nCol = -1;

  // Set up columns.
  COLUMN cols[OFS(4)][1];
  for (int n = 0; n < SIZE(cols); ++n) initColumn(cols[n], n, h);
  
  // Set up the pool of data objects and an allocation pointer.
  DATA data[2916][1];
  int dp = 0;
  
  // Build matrix.
  int nRow = 0;
  for (int i = 0; i < 9; ++i) {
    for (int j = 0; j < 9; ++j) {
      for (int v = 0; v < 9; ++v, ++nRow) {
        if (board[i][j] == '.' || board[i][j] == v + '1') {
          DATA *head = data[dp++];
          insertHead(head, cols[RC(i, j)], nRow);
          insert(data[dp++], cols[RV(i, v)], nRow, head);
          insert(data[dp++], cols[CV(j, v)], nRow, head);
          insert(data[dp++], cols[BV(BLK(i, j), v)], nRow, head);
        }
      }
    }
  }
  SUDOKU_EMITTER se[1] = {{{emitSudokuSoln}, board}};
  if (setjmp(se->done) == 0) search(h->data, NULL, se->emitter);
}

int main(void) {
  char a[9][9] = {
    ".........",
    ".........",
    ".........",
    ".........",
    ".........",
    ".........",
    ".........",
    ".........",
    ".........",
  };
  char b[9][9] = {
    ".3.2..4..",
    "25.1..9.7",
    ".....9..3",
    "4..9.26..",
    "7.......2",
    "..65.7..1",
    "5..8.....",
    "3.8..5.24",
    "..2..3.8.",
  };
  char c[9][9] = {
    ".7..4..6.",
    "4..5.8..1",
    "..8...5..",
    ".8.7.9.5.",
    "1.......9",
    ".9.8.3.1.",
    "..2...1..",
    "7..2.6..8",
    ".3..8..7.",
  };
  char (*board)[9] = c;
  solveSudoku(board);
  for (int i = 0; i < 9; ++i) printf("%.9s\n", board[i]);
  return 0;
}

Open source dancing links Algorithm X solvers I've looked at are verbose and even set up a 0/1 constraint matrix explicitly! The intent here is general purpose Algorithm X taken exactly from Knuth's paper with a concise setup builder for N-Queens and Sudoku problems.