NOIP2009最后一題。
看到題的時(shí)候直接就想到了DancingLinks，但是。。。很后悔是，原來(lái)想學(xué)的時(shí)候覺(jué)得難寫就沒(méi)寫了。
不過(guò)考試時(shí)裸搜加最優(yōu)性剪枝有95分，也很不錯(cuò)了。
DacingLinks其實(shí)就是十字鏈表，用于求解精確覆蓋問(wèn)題：對(duì)于一個(gè)0-1矩陣，選取一些行使得每列有且只有一個(gè)1。
把數(shù)獨(dú)轉(zhuǎn)換為這樣一個(gè)模型以后就可以用DacingLinks快速的搜索了。
搜索時(shí)每次選擇1的個(gè)數(shù)最少的那列，枚舉那列上選取的某行，再把那行其他位置有1的列刪除，接著繼續(xù)搜索。回溯時(shí)再還原改動(dòng)。
對(duì)于數(shù)獨(dú)而言，一共有9*9個(gè)格子，每個(gè)格子可以填9個(gè)數(shù)，所以在0-1矩陣?yán)锞陀?*9*9=729行，表示在某個(gè)格子里填某個(gè)數(shù)。
同時(shí)在某個(gè)位置填了某個(gè)數(shù)后，那個(gè)數(shù)所在的列，行，9宮格也不能填那個(gè)數(shù)了，同時(shí)那個(gè)格子也不能填其他數(shù)了，所以某行填某個(gè)數(shù)有9*9，某列填某個(gè)數(shù)有9*9，某個(gè)9宮格填某個(gè)數(shù)9*9，某個(gè)位置填數(shù)9*9，一共就用324列。
建好這樣一個(gè)圖后，就直接用DancingLinks搜索，因?yàn)橄啾纫话愕穆闼讶哂嗪苌伲运俣确浅？臁?br>
/*
* $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;
}