/* A classical Dancing Links Sudoku solver. */
#include <stdio.h>
#include <stdlib.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 insertFirst(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;
  DATA *i = c->d;
  while (i != c) {
    DATA *j = i->r;
    while (j != i) {
      j->d->u = j->u;
      j->u->d = j->d;
      --j->c->size;
      j = j->r;
    }
    i = i->d;
  }
}

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

static DATA *chooseNextColumn(DATA *h) {
  DATA *p = h->r;
  DATA *p_min = p;
  while (p != h) {
    if (p->c->size < p_min->c->size) p_min = p;
    p = p->r;
  }
  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);
  DATA *r = c->d;
  while (r != c) {
    DATA *j = r->r;
    while (j != r) {
      cover(j->c->data);
      j = j->r;
    }
    SOLUTION sNew[1] = {{ s, r }};
    search(h, sNew, emitter);
    c = r->c->data;
    j = r->l;
    while (j != r) {
      uncover(j->c->data);
      j = j->l;
    }
    r = r->d;
  }
  uncover(c);
}

// 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 RCV(R, C, V) S(S(R, C), V)
#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) % 9) / 3) * 3 + ((J) % 9) / 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;
  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) {
  // 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++];
          insertFirst(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[] = ".3.2..4..";
  char b[] = "25.1..9.7";
  char c[] = ".....9..3";
  char d[] = "4..9.26..";
  char e[] = "7.......2";
  char f[] = "..65.7..1";
  char g[] = "5..8.....";
  char h[] = "3.8..5.24";
  char i[] = "..2..3.8.";
  char *board[] = { a, b, c, d, e, f, g, h, i };
  solveSudoku(board);
  for (int i = 0; i < 9; ++i) printf("%s\n", board[i]);
  return 0;
}