#include #define SIZE 20 int sq[SIZE][SIZE]; int row[SIZE]; int col[SIZE]; int n; int allvec; int nrbitset(int x) { int r = 0; for (int i = 0; i < n; i++) if ((1 << i) & x) r++; return r; } void set(int i, int j, int k) { if (sq[i][j] != 0) { printf("%d %d %d %d\n", i, j, sq[i][j], k); exit(1); } sq[i][j] = k+1; row[i] &= ~(1 << k); col[j] &= ~(1 << k); } void iset(int i, int j, int k) { set(i-1,j-1,k-1); } void reset(int i, int j) { int k = sq[i][j]-1; sq[i][j] = 0; row[i] |= (1 << k); col[j] |= (1 << k); } int possiblemoves() { int p = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (sq[i][j] == 0) { int v = nrbitset(row[i] & col[j]); if (v == 0) return 0; p += v; // v*v - (v < 2 ? 0 : v-2); } return p; } int count = 0; bool solve(int depth) { printf("%*.*s%d\n", depth, depth, "", possiblemoves()); struct { int pm; int i; int j; int k; } sols[SIZE*SIZE*SIZE]; int nrsols = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (sq[i][j] == 0 && nrbitset(row[i] & col[j]) == 1) { int v = row[i] & col[j]; for (int k = 0; k < n; k++) if ((1 << k) & v) { set(i,j,k); if (solve(depth+1)) return true; reset(i,j); return false; } } int o = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (sq[i][j] == 0) { o++; int x = row[i] & col[j]; for (int k = 0; k < n; k++) if ((1 << k) & x) { set(i,j,k); int pm = possiblemoves(); reset(i,j); if (pm > 0) { int s; for (s = 0; s < nrsols; s++) if (sols[s].pm < pm) break; for (int t = nrsols; t > s; t--) sols[t] = sols[t-1]; sols[s].pm = pm; sols[s].i = i; sols[s].j = j; sols[s].k = k; nrsols++; } } } //printf("nrsols = %d\n", o); if (o == 0) { for (int j = n-1; j >= 0; j--) { for (int i = 0; i < n; i++) printf("%3d", sq[i][j]); printf("\n"); } if (count++ > 1000) return true; //return true; } for (int s = 0; s < nrsols && s < 2; s++) { //printf("Try %d,%d,%d %d\n", sols[s].i+1, sols[s].j+1, sols[s].k+1, sols[s].pm); set(sols[s].i, sols[s].j, sols[s].k); if (solve(depth+1)) return true; reset(sols[s].i, sols[s].j); } return false; } int main(int argc, char *argv[]) { n = 9; allvec = (2 << n) - 1; for (int i = 0; i < n; i++) { row[i] = allvec; col[i] = allvec; for (int j = 0; j < n; j++) sq[i][j] = 0; } iset(1,1,1); iset(2,3,1); iset(4,3,4); iset(4,5,1); iset(4,8,5); iset(6,4,2); iset(6,7,6); iset(7,6,2); iset(8,3,3); solve(9); return 0; }