这部分代码是从另外一个C++的程序里移植过来的，一时找不到原C++代码的连接了，但是从C#的代码反推C++的代码并不是什么问题，当时移植这段代码也没废什么功夫。
使用DLX（Dancing Link X）解决数独这个Exact Cover（精确覆盖）问题，是一个很常见的方法。类似的代码有比较多。但是也有相当的人是利用尝试和回溯的办法来解题的。
现在的计算机计算效率已经非常的高了，而数独的9X9的方阵也的确没多少数据量，所以站在人的角度，并不能感受两种解题方法在速度上的差异。
但是在生成数独题的过程中，会需要非常多的次数来重复解题，所以解题的时间自然是越快越好的。
我将KLSudoku里这个部分的代码单独在这里贴出，而完整的代码可以从项目主页SVN TAB上浏览看到：http://code.google.com/p/klsudoku
（奇怪，不能插入代码，只好直接贴了）
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using System.Diagnostics;
using System.Collections;
using System.IO;
using System.Xml;
/*
* Project Home : http://code.google.com/p/klsudoku
* Project Owner: ttylikl@gmail.com Email:ttylikl@qq.com
* Project Blog : http://www.cnblogs.com/ttylikl
* All Files of this project is free to use , but you should keep the information above when you copy&use it.
* Infomation Modify Date: 2009.02.22
*
* */
namespace SudokuPanel
{
public class dlx_solver
{
const int RR = 729;
const int CC = 324;
const int INF = 1000000000;
int[] mem = new int[RR + 9];
int[] ans = new int[RR + 9];
char[] ch = new char[RR + 9];
int[] cnt = new int[CC + 9];
class node
{
public int r, c;
public node up;
public node down;
public node left;
public node right;
};
node head;
node[] all = new node[RR * CC + 99];
node[] row = new node[RR];
node[] col = new node[CC];
int all_t;
void link(int r, int c)
{
cnt[c]++;
node t = all[all_t];
if (t == null)
{
t = new node();
all[all_t] = t;
}
all_t++;
t.r = r;
t.c = c;
t.left = row[r];
t.right = row[r].right;
t.left.right = t;
t.right.left = t;
t.up = col[c];
t.down = col[c].down;
t.up.down = t;
t.down.up = t;
}
void remove(int c)
{
node t, tt;
col[c].right.left = col[c].left;
col[c].left.right = col[c].right;
for (t = col[c].down; !Object.ReferenceEquals(t, col[c]); t = t.down)
{
for (tt = t.right; !Object.ReferenceEquals(tt, t); tt = tt.right)
{
cnt[tt.c]--;
tt.up.down = tt.down;
tt.down.up = tt.up;
}
t.left.right = t.right;
t.right.left = t.left;
}
}
void resume(int c)
{
node t, tt;
for (t = col[c].down; !Object.ReferenceEquals(t, col[c]); t = t.down)
{
t.right.left = t;
t.left.right = t;
for (tt = t.left; !Object.ReferenceEquals(tt, t); tt = tt.left)
{
cnt[tt.c]++;
tt.down.up = tt;
tt.up.down = tt;
}
}
col[c].left.right = col[c];
col[c].right.left = col[c];
}
int solve(int k)
{
if (Object.ReferenceEquals(head.right, head))
return 1;
node t, tt;
int min = INF, tc=0;
for (t = head.right; !Object.ReferenceEquals(t, head); t = t.right)
{
if (cnt[t.c] < min)
{
min = cnt[t.c];
tc = t.c;
if (min <= 1) break;
}
}
remove(tc);
int scnt = 0;
for (t = col[tc].down; !Object.ReferenceEquals(t, col[tc]); t = t.down)
{
//if (mem[k] != 0)
// Debug.Write("");
mem[k] = t.r;
t.left.right = t;
for (tt = t.right; !Object.ReferenceEquals(tt, t); tt = tt.right)
{
remove(tt.c);
}
t.left.right = t.right;
scnt += solve(k + 1);
if (!chk_unique && scnt ==1)
return scnt;
if (scnt > 1)
return scnt;
//继续找下一个可能
t.right.left = t;
for (tt = t.left; !Object.ReferenceEquals(tt, t); tt = tt.left)
{
resume(tt.c);
}
t.right.left = t.left;
}
resume(tc);
return scnt;
}
private bool chk_unique = false;
public int scount=0;
public int solution_count(String str)
{
chk_unique=true;
run(str);
return scount;
}
public String do_solve(String str)
{
chk_unique = false;
String ret=run(str);
if (scount != 1)
return "";
return ret;
}
private String run(String str)
{
mem = new int[RR + 9];
ans = new int[RR + 9];
ch = new char[RR + 9];
//Debug.WriteLine("dlx_solve(" + str + ")");
String s=str.Replace("\r","");
s=s.Replace("\n","");
ch = s.ToCharArray();
cnt = new int[CC + 9];
head = new node();
all = new node[RR * CC + 99];
row = new node[RR];
col = new node[CC];
/*while(gets(ch))*/
{
int i;
//if(ch[0]=='e')break;
all_t = 1;
cnt = new int[CC + 9];
head.left = head;
head.right = head;
head.up = head;
head.down = head;
head.r = RR;
head.c = CC;
for (i = 0; i < CC; i++)
{
col[i] = new node();
col[i].c = i;
col[i].r = RR;
col[i].up = col[i];
col[i].down = col[i];
col[i].left = head;
col[i].right = head.right;
col[i].left.right = col[i];
col[i].right.left = col[i];
}
for (i = 0; i < RR; i++)
{
row[i] = new node();
row[i].r = i;
row[i].c = CC;
row[i].left = row[i];
row[i].right = row[i];
row[i].up = head;
row[i].down = head.down;
row[i].up.down = row[i];
row[i].down.up = row[i];
}
for (i = 0; i < RR; i++)
{
int r = i / 9 / 9 % 9;
int c = i / 9 % 9;
int val = i % 9 + 1;
if (ch[r * 9 + c] == '.' || ch[r * 9 + c] == '0' || ch[r * 9 + c] == val + '0')
{
link(i, r * 9 + val - 1);
link(i, 81 + c * 9 + val - 1);
int tr = r / 3;
int tc = c / 3;
link(i, 162 + (tr * 3 + tc) * 9 + val - 1);
link(i, 243 + r * 9 + c);
}
}
for (i = 0; i < RR; i++)
{
row[i].left.right = row[i].right;
row[i].right.left = row[i].left;
}
scount = solve(1);
for (i = 1; i <= 81; i++)
{
int t = mem[i] / 9 % 81;
int val = mem[i] % 9 + 1;
//Debug.WriteLine("t=" + t.ToString("00")+ "mem[" + i.ToString("D2")+ "]="+mem[i]+" val=" + val + "i=" + i.ToString("D2"));
ans[t] = val;
}
StringBuilder sb = new StringBuilder();
for (i = 0; i < 81; i++)
{
//Debug.Write(ans[i]);
//if (ans[i] == 0)
// Debug.Write("val=0!");
sb.Append(ans[i]);
}
//Debug.WriteLine("");
//Debug.WriteLine("scnt=" + solution_count);
return sb.ToString();
}
}
}
}