数独游戏(C++)

#include "stdio.h" #include <iostream> #define N 25 int row[N + 1], col[N + 1], blk[N + 1], data[N + 1][N + 1]; int Emp[N * N][3], size[65536], mark[65536], decided[N * N]; int Flag, n, m, count, top; int leftNum(int x) { int i=0; do{ if(x&1)i++; } while(x>>=1); return i; } int decPos(int x) { int i = 0; while( x && !(x & 1) ) x >>= 1, ++i; return 1 << i; } bool Judge(int r,int c,int b,int pos) { return ((row[r]&pos)!= pos||(col[c]&pos)!=pos||(blk[b]&pos)!=pos); } void setPos(int r,int c,int b,int pos) { row[r] ^= pos; col[c] ^= pos; blk[b] ^= pos; } int init(){ int i, j, pos; for(i = Flag = 0; i < m; ++i) Flag = (Flag << 1) | 1; for(i = 0; i < m; ++i) row[i] = col[i] = blk[i] = Flag; top = 0; for(i = 0; i < m; ++i){ for(j = 0; j < m; ++j){ if( data[i][j] != 0 ){ pos = 1 << (data[i][j] - 1); if( Judge(i, j, i / n * n + j / n, pos) ) return 0; setPos(i, j, i / n * n + j / n, pos); } else{ Emp[top][0] = i; Emp[top][1] = j; Emp[top][2] = i / n * n + j / n; ++top; } } } return 1; } void Search(int cnt){ int cur, min = Flag, s; for(int i = 0; i < top; ++i){ if(decided[i]==0){ s = size[ row[Emp[i][0]] & col[Emp[i][1]] & blk[Emp[i][2]] ]; if(s < min){ min = s; cur = i; } } } if(!min) return; decided[cur] = 1; int r = Emp[cur][0], c = Emp[cur][1], b = Emp[cur][2]; int status = row[r] & col[c] & blk[b]; if(cnt + 1 >= top) count += size[status]; else{ do{ setPos(r, c, b, mark[status]); Search(cnt + 1); setPos(r, c, b, mark[status]); }while(status &= status - 1); } decided[cur] = 0; } int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); memset( decided, 0, 4*N*N); count = 0; for(int k = 0; k < 65536; ++k){ mark[k] = decPos(k); size[k] = leftNum(k); } scanf("%d", &n); m = n * n; for(int i = 0; i < m; ++i) for(int j = 0; j < m; ++j) scanf("%d", &data[i][j]); if( init()==1 ){ if(n == 5) printf("1\n"); else{ if( top != 0 ) Search(0); printf("%d\n", count); } } else printf("0\n"); return 0; }