#include #define SIZE 20 int sq[SIZE][SIZE]; int allowed[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] & allowed[i][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; sols.pm = 0; int v; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (sq[i][j] == 0 && nrbitset(v = row[i] & col[j] & allowed[i][j]) == 1) { 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] & allowed[i][j]; for (int k = 0; k < n; k++) if ((1 << k) & x) { set(i,j,k); int pm = possiblemoves(); reset(i,j); if (pm > sols.pm) { sols.pm = pm; sols.i = i; sols.j = j; sols.k = k; } } } //printf("nrsols = %d\n", o); if (o == 0) { #if 0 for (int j = n-1; j >= 0; j--) { for (int i = 0; i < n; i++) printf("%3d", sq[i][j]); printf("\n"); } #else for (int j = n-1; j >= 0; j--) { for (int i = 0; i < n; i++) printf("%1d", sq[i][j]); } printf("\n"); #endif if (count++ > 100000) return true; //return true; } if (sols.pm > 0) { set(sols.i, sols.j, sols.k); if (solve(depth+1)) return true; reset(sols.i, sols.j); allowed[sols.i][sols.j] &= ~(1 << sols.k); if (solve(depth+1)) return true; allowed[sols.i][sols.j] |= (1 << sols.k); } 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; allowed[i][j] = allvec; } } 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; }