【POJ 3074】Sudoku

题目传送门:http://poj.org/problem?id=3074

Dancing_links

#include<iostream>
#include<cstdio>
using namespace std;

char pat[90];
int grid[10][10]={
	{0,0,0,0,0,0,0,0,0,0},
	{0,1,1,1,4,4,4,7,7,7},
	{0,1,1,1,4,4,4,7,7,7},
	{0,1,1,1,4,4,4,7,7,7},
	{0,2,2,2,5,5,5,8,8,8},
	{0,2,2,2,5,5,5,8,8,8},
	{0,2,2,2,5,5,5,8,8,8},
	{0,3,3,3,6,6,6,9,9,9},
	{0,3,3,3,6,6,6,9,9,9},
	{0,3,3,3,6,6,6,9,9,9}
};

namespace Dancing_link{
	#define DL Dancing_link
	const int MX = 324;
	const int N = 1000000;
	int rma,cnt,L[N],R[N],U[N],D[N],sz[N],col[N],p[N],v[N];
	
	
	inline void init(){
		rma = 0; cnt = MX;
		for (int i=0;i<=MX;i++) L[i] = i-1, R[i] = i+1, U[i] = i, D[i] = i, sz[i] = 0;
		L[0] = MX; R[MX] = 0;
	}
	
	inline void AddRow(int n, int pos, int val, int *arr){
		for (int i=1,w;i<=n;i++) {
			w = ++cnt; p[w] = pos; v[w] = val;
			col[w] = arr[i]; sz[arr[i]]++;
			L[w+1] = w; R[w] = w+1; 
			D[U[arr[i]]] = w; D[w] = arr[i];
			U[w] = U[arr[i]]; U[arr[i]] = w; 
		}
		L[cnt-n+1] = cnt; R[cnt] = cnt-n+1;
	}
	
	inline void remove(int w){
		L[R[w]] = L[w];
		R[L[w]] = R[w];
		for (int i=D[w];i!=w && i;i=D[i]) for (int j=R[i];j!=i;j=R[j])
			D[U[j]] = D[j], U[D[j]] = U[j], sz[col[j]]--;
	}
	
	inline void restore(int w){
		for (int i=U[w];i!=w && i;i=U[i]) for (int j=L[i];j!=i;j=L[j])
			D[U[j]] = j, U[D[j]] = j, sz[col[j]]++;
		L[R[w]] = w;
		R[L[w]] = w;
	}
	
	bool solve(int d){
		if (d == rma+1) return true;
		
		int w = R[0];
		for (int i=R[w];i;i=R[i]) if (sz[i] < sz[w]) w = i;
		
		remove(w);
		for (int i=D[w];i!=w;i=D[i]) {
			pat[p[i]] = v[i]+'0'; 
			for (int j=R[i];j!=i;j=R[j]) remove(col[j]);
			if (solve(d+1)) return true;
			for (int j=R[i];j!=i;j=R[j]) restore(col[j]); 
		}
		restore(w);
		
		return false;
	}
};

inline int ID(int t, int pos, int val) {
	return 81*(t-1)+9*(pos-1)+val;
}

inline void build_link(){
	static int tmp[10]; DL::init();
	for (int j=1,w=1;j<=9;j++) for (int i=1;i<=9;i++,w++) if (pat[w] == '.') {
		for (int k=1;k<=9;k++) {
			tmp[1] = ID(1,i,k);
			tmp[2] = ID(2,j,k);
			tmp[3] = ID(3,grid[i][j],k);
			tmp[4] = 243+w;
			DL::AddRow(4,w,k,tmp);
		}
		DL::rma++; 
	}
	 for (int j=1,w=1;j<=9;j++) for (int i=1;i<=9;i++,w++) if (pat[w] != '.') { 
		int c = pat[w]-'0';
		DL::remove(ID(1,i,c));
		DL::remove(ID(2,j,c));
		DL::remove(ID(3,grid[i][j],c));
		DL::remove(243+w);
	}
}

int main(){
	while (~scanf("%s",pat+1) && pat[1] != 'e') {
		build_link();
		if (DL::solve(1)) printf("%s\n",pat+1);
		else printf("No solution\n");
	}
	return 0;
}