NOIP2009最后一题。
看到题的时候直接就想到了DancingLinks，但是。。。很后悔是，原来想学的时候觉得难写就没写了。
不过考试时裸搜加最优性剪枝有95分，也很不错了。
DacingLinks其实就是十字链表，用于求解精确覆盖问题：对于一个0-1矩阵，选取一些行使得每列有且只有一个1。
把数独转换为这样一个模型以后就可以用DacingLinks快速的搜索了。
搜索时每次选择1的个数最少的那列，枚举那列上选取的某行，再把那行其他位置有1的列删除，接着继续搜索。回溯时再还原改动。
对于数独而言，一共有9*9个格子，每个格子可以填9个数，所以在0-1矩阵里就有9*9*9=729行，表示在某个格子里填某个数。
同时在某个位置填了某个数后，那个数所在的列，行，9宫格也不能填那个数了，同时那个格子也不能填其他数了，所以某行填某个数有9*9，某列填某个数有9*9，某个9宫格填某个数9*9，某个位置填数9*9，一共就用324列。
建好这样一个图后，就直接用DancingLinks搜索，因为相比一般的裸搜冗余很少，所以速度非常快。
/*
* $File: sudoku.cpp
* $Date: Sun Nov 29 20:22:32 2009 CST
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define LENGTH 9
#define SQRLEN 3
#define MAXN (LENGTH*LENGTH*LENGTH)
#define MAXM (4*LENGTH*LENGTH)
#define MAXNODE MAXN*MAXM
int max(int a,int b){
return a>b?a:b;
}
int map[MAXN][MAXM];
int U[MAXNODE],D[MAXNODE],L[MAXNODE],R[MAXNODE];
int S[MAXNODE],C[MAXNODE],ROW[MAXNODE];
int n,m;
int h = 0;//the Leftest and Upest node
int a[LENGTH][LENGTH];
void Init(){
freopen("sudoku.in","r",stdin);
freopen("sudoku.out","w",stdout);
for (int i = 0; i<LENGTH; i++)
for (int j = 0; j<LENGTH; j++)
scanf("%d",&a[i][j]);
}
int Row(int x,int y,int num){
return (x*LENGTH+y)*LENGTH+num-1;
}
#define SEC_POS 0
#define SEC_ROW 1
#define SEC_COL 2
#define SEC_SQR 3
#define PER_SEC LENGTH*LENGTH
void Fill(int x,int y,int num){
int row = Row(x,y,num);
map[row][SEC_POS*PER_SEC+x*LENGTH+y] = 1;
map[row][SEC_ROW*PER_SEC+x*LENGTH+num-1] = 1;
map[row][SEC_COL*PER_SEC+y*LENGTH+num-1] = 1;
map[row][SEC_SQR*PER_SEC+((x/SQRLEN)*SQRLEN+(y/SQRLEN))*LENGTH+num-1] = 1;
}
int cnt;
void BuildGraph(){
// Build The 0-1 Matrix
for (int i = 0; i<LENGTH; i++)
for (int j = 0; j<LENGTH; j++)
if (a[i][j])
Fill(i,j,a[i][j]);
else for (int k = 1; k<=LENGTH; k++)
Fill(i,j,k);
// Build Dacing Links
n = MAXN,m = MAXM;
for (int i = 0; i<n; i++)
for (int j = 0; j<m; j++)
if (map[i][j])
map[i][j] = ++cnt;
int tmp,s = 0,t = 0;
for (int i = 0; i<n; i++){
for (int j = 0; j<m; j++)
if (tmp=map[i][j])
L[tmp] = t, S[tmp] = i,t = tmp;
for (int j = m-1; j>=0; j--)
if (tmp=map[i][j])
R[tmp] = s, s =tmp;
R[t] = s,L[s] = t;
}
for (int j = 0; j<m; j++){
t = ++cnt;
for (int i = 0; i<n; i++)
if (tmp=map[i][j])
U[tmp] = t, t = tmp,C[tmp] = cnt, ++S[cnt];
s = cnt;
for (int i = n-1; i>=0; i--)
if (tmp=map[i][j])
D[tmp] = s, s = tmp;
D[cnt] = s,U[cnt] = t;
}
for (int i = cnt-m+1; i<=cnt; i++)
L[i] = i-1;
for (int i = cnt; i>cnt-m; i--)
R[i] = i+1;
R[h] = cnt-m+1,L[h] = cnt;
L[cnt-m+1] = R[cnt] = h;
}
int ans[MAXM+1];
void Cover(int c){
L[R[c]] = L[c],R[L[c]] = R[c];
for (int i = D[c];i!=c;i = D[i])
for (int j = R[i];j!=i;j = R[j])
U[D[j]] = U[j],D[U[j]] = D[j],S[C[j]]--;
}
void UnCover(int c){
for (int i = U[c];i!=c;i=U[i])
for (int j = L[i];j!=i;j = L[j])
S[C[j]]++,U[D[j]] = D[U[j]] = j;
L[R[c]] = R[L[c]] = c;
}
int Ans = -1;
int ScoreTable[LENGTH][LENGTH] = {
{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}
};
int score(int c){
int t = S[c];
int num = t%LENGTH+1;
int x = t/LENGTH/LENGTH%LENGTH;
int y = t/LENGTH%LENGTH;
return num*ScoreTable[x][y];
}
int ansmap[LENGTH][LENGTH];
//this function is not used in this program, but it gives out a solution of a sudoku
void GetAns(int step){
memset(ansmap,0,sizeof(ansmap));
for (int i = 0; i<step; i++){
int t = ans[i];
int x = t/LENGTH/LENGTH%LENGTH;
int y = t/LENGTH%LENGTH;
int num = t%LENGTH+1;
ansmap[x][y] = num;
}
}
void search(int step,int v){
if (R[h] == h){
Ans = max(Ans,v);
/* GetAns(step);
for (int i = 0; i<LENGTH; i++){
for (int j = 0; j<LENGTH; j++)
printf("%d ",ansmap[i][j]);
printf("\n");
}
printf("\n");*/
return;
}
int c,s = MAXNODE;
for (int i = R[h];i!=h; i=R[i])
if (S[i]<s)
s = S[i],c = i;
Cover(c);
for (int i = D[c];i!=c;i=D[i]){
ans[step] = S[i];
for (int j = R[i];j!=i;j = R[j])
Cover(C[j]);
search(step+1,v+score(i));
for (int j = L[i];j!=i;j = L[j])
UnCover(C[j]);
}
UnCover(c);
}
void DancingLinks(){
search(0,0);
printf("%d\n",Ans);
}
void Solve(){
BuildGraph();
DancingLinks();
}
int main(){
Init();
Solve();
return 0;
}