#include #include #include using namespace std; const int maxn=81*4+5; const int maxnode=9*9*9*4*4+5; const int Slot=0,Row=1,Col=2,Sub=3; const int p[9][9]= { {6,6,6,6,6,6,6,6,6}, {6,7,7,7,7,7,7,7,6}, {6,7,8,8,8,8,8,7,6}, {6,7,8,9,9,9,8,7,6}, {6,7,8,9,10,9,8,7,6}, {6,7,8,9,9,9,8,7,6}, {6,7,8,8,8,8,8,7,6}, {6,7,7,7,7,7,7,7,6}, {6,6,6,6,6,6,6,6,6} }; inline int encode(int a,int b,int c) { return a*81+b*9+c+1; } inline void decode(int code,int &a,int &b,int &c) { code--; c=code%9; code/=9; b=code%9; code/=9; a=code; } int res=-1,mp[9][9]; struct DLX { int n,sz; int s[maxn]; int row[maxnode],col[maxnode]; int L[maxnode],R[maxnode],U[maxnode],D[maxnode]; void init(int n) { this->n=n; sz=n+1; memset(s,0,sizeof(s)); for(int i=0;i<=n;i++) { U[i]=i; D[i]=i; L[i]=i-1; R[i]=i+1; } R[n]=0; L[0]=n; } void addNodes(int r,const vector &columns) { int first=sz,c_sz=columns.size(); for(int i=0;i cols; cols.push_back(encode(Slot,r,c)); cols.push_back(encode(Row,r,v)); cols.push_back(encode(Col,c,v)); cols.push_back(encode(Sub,(r/3)*3+c/3,v)); solver.addNodes(encode(r,c,v),cols); } solver.dfs(0); printf("%d\n",res); return 0; }