Sudoku/C

<lang c>#include <stdio.h>

1. if 1
2. define N 4

int x[][N*N] = { { 6, 0, 7, 0, 0, 11, 0, 8, 1, 14, 15, 16, 0, 5, 2, 0}, { 0, 10, 5, 0, 14, 0, 0, 0, 0, 0, 11, 3, 8, 0, 15, 0}, { 0, 0, 16, 0, 0, 0, 0, 7, 0, 0, 9, 0, 12, 4, 0, 14}, { 0, 13, 0, 0, 9, 0, 0, 12, 0, 5, 0, 0, 0, 0, 0, 16}, { 0, 0, 0, 10, 0, 0, 13, 11, 2, 0, 0, 0, 3, 12, 0, 0}, { 12, 0, 9, 0, 8, 0, 0, 0, 16, 0, 0, 13, 0, 11, 0, 0}, { 7, 0, 0, 14, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 13, 2}, { 13, 0, 0, 8, 1, 0, 0, 5, 0, 7, 0, 11, 16, 0, 10, 0}, { 0, 15, 0, 11, 5, 0, 7, 0, 3, 0, 0, 6, 2, 0, 0, 10}, { 1, 4, 0, 0, 0, 13, 0, 0, 0, 0, 0, 0, 15, 0, 0, 12}, { 0, 0, 6, 0, 12, 0, 0, 14, 0, 0, 0, 15, 0, 3, 0, 4}, { 0, 0, 8, 3, 0, 0, 0, 6, 5, 1, 0, 0, 13, 0, 0, 0}, { 3, 0, 0, 0, 0, 0, 12, 0, 8, 0, 0, 4, 0, 0, 16, 0}, { 10, 0, 13, 4, 0, 5, 0, 0, 11, 0, 0, 0, 0, 8, 0, 0}, { 0, 12, 0, 2, 4, 8, 0, 0, 0, 0, 0, 5, 0, 13, 7, 0}, { 0, 16, 1, 0, 7, 9, 3, 13, 14, 0, 10, 0, 0, 15, 0, 11} };

1. else
2. define N 3

int x[][N * N] = { { 5, 0, 0, 0, 7, 0, 0, 0, 0 }, { 6, 0, 0, 1, 9, 5, 0, 0, 0 }, { 0, 9, 8, 0, 0, 0, 0, 6, 0 }, { 8, 0, 0, 0, 6, 0, 0, 0, 3 }, { 4, 0, 0, 8, 0, 3, 0, 0, 1 }, { 7, 0, 0, 0, 2, 0, 0, 0, 6 }, { 0, 6, 0, 0, 0, 0, 2, 8, 0 }, { 0, 0, 0, 4, 1, 9, 0, 0, 5 }, { 0, 0, 0, 0, 8, 0, 0, 7, 9 } };

1. endif

1. define W (N * N)

int ptr, used[W][W], bits[256]; struct { int *p, v; } rec[W * W * W * 3];

inline int countbits(int v) { int c = 0; while (v) { c += bits[v & 255]; v >>= 8; } return W - c; }

void show() { int i, j; for (i = 0; i < W; i++) { if (!(i % N)) putchar('\n'); for (j = 0; j < W; j++) printf(j % N ? "%3d" : "%4d", x[i][j]); putchar('\n'); }

return; }

void save(int *p, int v) { rec[ptr].p = p, rec[ptr].v = *p; *p = v; ptr++; }

void restore(int i) { while (ptr > i) { --ptr; rec[ptr].p[0] = rec[ptr].v; } }

int setcell(int row, int col, int v) { int i, j, b = 1 << (v - 1), c, r; int cur = ptr;

if (used[row][col] & (1 << (v - 1))) { restore(cur); return 0; }

save(used[row] + col, (1 << W) - 1); save(x[row] + col, v);

for (i = 0; i < W; i++) if (i != col && !(used[row][i] & b)) save(used[row] + i, used[row][i] | b);

for (i = 0; i < W; i++) if (i != row && !(used[i][col] & b)) save(used[i] + col, used[i][col] | b);

r = row / N * N; c = col / N * N; for (i = r; i < r + N; i++) { if (i == row) continue; for (j = c; j < c + N; j++) if (j != col && !(used[i][j] & b)) save(used[i] + j, used[i][j] | b); }

return 1; }

int tryfill() { int i, j, bi, bj, least = W + 1; int u, cur = ptr;

for (i = 0; i < W; i++) { for (j = 0; j < W; j++) { if (x[i][j]) continue; if (!(u = countbits(used[i][j]))) return 0;

if (u < least) { least = u, bi = i, bj = j; if (least == 1) goto done; } } }

if (least == W + 1) return 1;

done: u = used[bi][bj]; for (i = 0; i < W; i++) { if (u & (1 << i)) continue;

setcell(bi, bj, i + 1); if (tryfill()) return 1;

restore(cur); } return 0; }

int solve() { int i, j; for (i = 0; i < W; i++) for (j = 0; j < W; j++) if (x[i][j] && !setcell(i, j, x[i][j])) return 0;

ptr = 0; tryfill();

return 1; }

void initbitcount() { int v, i, b, c; for (v = 0; v < 256; v++) { for (b = 1, c = i = 0; i < 8; i++, b <<= 1) if (b & v) c++; bits[v] = c; } }

int main(void) { initbitcount(); if (solve()) show(); else puts("no solution");

return 0; }</lang>