原文链接：http://www.zerob13.in/2009/10/30/java%E7%9A%84dance-links%E8%A7%A3%E6%95%B0%E7%8B%AC/
package com.zerob13.Sudoku;
import java.util.*;
/**
* @author yanglingfeng
*
*/
class node{
public int x,y,l,r,u,d;
public int sum;
public int f;
public char now;
public node(){
x=0;
y=0;
l=0;
r=0;
u=0;
d=0;
sum=0;
f=0;
now=0;
}
}
public class Sudoku {
private int n,m;
private int cnt;
private char[][] map;
private int x;
private int y;
private char nn;
node[] p;
public Sudoku(){
n=9*9*9+1;
m=9*9*4+1;
int i,j,k;
boolean[][] row,col,cube;
row=new boolean[9][19];
col=new boolean[9][19];
cube=new boolean[9][19];
map=new char[29][29];
Scanner read=new Scanner(System.in);
String a;
int L=0;
for(i=0;i<9;i++){
a=read.nextLine();
L=0;
for(j=0;j<a.length();j++)
{
if(a.charAt(j)!=' ')
map[i][L++]=a.charAt(j);
}
}
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(map[i][j]!='?')
{
row[i][map[i][j] - '1'] = true;
col[j][map[i][j] - '1'] = true;
cube[i / 3 * 3 + j / 3][map[i][j] - '1'] = true;
}
}
}
p=new node[n*m];
for(i=0;i<n*m;i++)
{
p[i]=new node();
}
p[0].l=324;
p[0].r=1;
for(i=1;i<325;i++)
{
p[i].l=i-1;
p[i].r=i+1;
p[i].sum=0;
p[i].u=p[i].d=i;
}
p[324].r=0;
cnt=325;
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(map[i][j]!='?')
{
delnode(i * 9 + j + 1);
int tx = map[i][j] - '1';
delnode(81 + (i + 1) + 9 * tx);
delnode(162 + (j + 1) + 9 * tx);
delnode(243 + (i / 3 * 3+ j / 3 + 1)+ 9 * tx );
}else
{
nn='1';
x=i;
y=j;
for(k=0;k<9;k++,nn++)
{
if (row[i][k]||col[j][k]||cube[i / 3 * 3 + j / 3][k])
continue;
int cnum = cnt;
addnode(i * 9 + j + 1);
addnode(81 + (i + 1) + 9 * k);
addnode(162 + (j + 1) + 9 * k);
addnode(243 + (i / 3 * 3+ j / 3 + 1)+9 * k );
p[cnum].l = cnt - 1;
p[cnt - 1].r = cnum;
}
}
}
}
dfs(0);
}
void addnode(int fa){
p[cnt].x=x;
p[cnt].y=y;
p[cnt].f=fa;
p[cnt].now=nn;
p[cnt].u=p[fa].u;
p[cnt].d=fa;
p[fa].sum++;
p[p[fa].u].d=cnt;
p[fa].u=cnt;
p[cnt].l=cnt-1;
p[cnt].r=cnt+1;
cnt++;
return ;
}
void delnode(int c)
{
p[p[c].l].r=p[c].r;
p[p[c].r].l=p[c].l;
}
void remove(int c)
{
p[p[c].l].r=p[c].r;
p[p[c].r].l=p[c].l;
int i,j;
for(i=p[c].d;i!=c;i=p[i].d)
{
for(j=p[i].r;j!=i;j=p[j].r)
{
p[p[j].f].sum--;
p[p[j].u].d=p[j].d;
p[p[j].d].u=p[j].u;
}
}
}
void resume(int c)
{
int i,j;
for(i=p[c].u;i!=c;i=p[i].u)
{
for(j=p[i].l;j!=i;j=p[j].l)
{
p[p[j].f].sum++;
p[p[j].u].d=j;
p[p[j].d].u=j;
}
}
p[p[c].r].l=c;
p[p[c].l].r=c;
}
boolean dfs(int k)
{
int i,j,minx=p[0].r;
if(p[0].r==0)
{
for(i=0;i<9;i++)
{
for(j=0;j<9;j++)
{
if(j!=0)
System.out.print(" "+map[i][j]);
else
System.out.print(map[i][j]);
}
System.out.println();
}
return true;
}
for(i=p[0].r;i!=0;i=p[i].r)
{
if(p[i].sum<p[minx].sum)
minx=i;
}
remove(minx);
for(i=p[minx].d;i!=minx;i=p[i].d)
{
map[p[i].x][p[i].y]=p[i].now;
for(j=p[i].r;j!=i;j=p[j].r)
{
remove(p[j].f);
}
if(dfs(k+1))
{
return true;
}
for(j=p[i].l;j!=i;j=p[j].l)
{
resume(p[j].f);
}
}
resume(minx);
return false;
}
}