KLSudoku可以根据用户的要求来生成不同难度的题目来进行游戏，这是如何做到的呢？
其实只要弄清楚几个关键问题就可以：
- 如何生成题目？
- 如何定义题目的难度？
- 最后是如何产生指定难度的题目？
如何生成题目
首先我们看看如何生成题目，我想到了两个方法：
第一个方法是：
- 在空白的数格里随机开始填数，每填上一个数就检查是否有解，如果无解则撤销填数，否则继续尝试下一个数
- 在这个过程中，如果得到了一个唯一解的局面，就可以得出一到题目了
上面的想法很自然，但是仔细想想很有可能尝试全部数格后，依然是很可能无法得到一个唯一解的题目。于是又产生了第二个想法。
第二个方法是：
- 先在9X9的数格里随机的放上N个数格。然后使用非逻辑的方法解出最终解。比如简单的递归回溯尝试每个数格的候选数。在KLSudoku里则是用DLX解法来完成这个步骤，因为在尝试的过程中会多次调用到这个解法，其实现的效率还是相对比较重要一些的，一定要尽量的快。
- 在得出终盘局面后，开始按随机的顺序将一个数格里的数字移除，然后再次判断是否有解（此时如果有解，一定是唯一解），如果无解，则将该数字放回去。
- 这样遍历完81个数字后，剩余的数字就构成了一个有效的数独初始局面了。
当然，还可以在软件发布的时候附带上数十万个题目，然而这并不能完全解决问题。而上面的两个方法显然第二个要更优一些，因为它更容易成功得出一个题目。
如何判断题目难度
好，现在题目已经生成了，该如何判断题目的难度呢？
这里提到的题目难度，是针对游戏玩家而言的，并不是针对解题器程序的，所以题目的难易，应该站在用户的角度上来看。
在KLSudoku里，除了快速解题的dlx_solver类，还实现了使用一个基于玩家可以使用的技巧进行解题的solver类。
solver类实现了常见的唯一数法，隐式和显式数集法，各种Wing和Fish以及Chain等解题技巧。
当我们生成题目后，就可以用solver类进行一次解题，统计解题过程中使用到的技巧，然后根据用户手动解题时应用这些技巧的难易程度来对生成的题目进行评分。这样就可以得出一道数独题的难度级别了。
可是，这样就能达到我们的目的了吗？我们可以根据用户的需要得出指定难度的题目了吗？答案是不！因为我们并不能控制生成题目的难度！
如何根据指定难度来出题游戏
我们必须要注意到，用户进行游戏的过程中，经常需要思考，对软件不会有太多的操作交互。
于是我们可以采取一个策略，就是用户需要的题目是从软件的题库里提取，而软件题库里的题，则在KLSudoku开始运行后，在后台起一个工作线程，不停的生成题目，然后逻辑解题，判断难度，然后根据难度存放到各个难度的题库里去。这样就完全解决了快速生成用户需要的题目的问题啦。
KLSudoku题目生成的过程就是这样简单的了。虽然显得有些笨拙，不过却是简单有效。不管黑猫白猫，能抓住老鼠不就是好猫，你说是不？
好了，附上dlx_solver.cs和generator.cs来，至于逻辑解题的solver.cs，实在太长了（2000多行），感兴趣的朋友从svn去看看吧
Codeusing 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.Runtime.InteropServices;
/*
* 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 Infomation Modify Date: 2009.02.22
*
* */
namespace SudokuPanel
{
public class SudokuGenerator
{
private Random ro = new Random();
public String do_dlx_generator(ref String str)
{
puzzle pz=new puzzle();
dlx_solver ds = new dlx_solver();
int[] remove = new int[81];
for (int i = 0; i < 81; ++i)
{
remove[i] = i;
}
for (int i = 0; i < 81; ++i)
{
int ri = ro.Next(0, 81);
if (ri != i)
{
int t = remove[ri];
remove[ri] = remove[i];
remove[i] = t;
}
}
while (true)
{
pz = new puzzle();
for (int i = 0; i < 17; ++i)//可以认为17个数必然有解，最少初始数的数独题也有17+的数字
{
int x = remove[i] / 9;
int y = remove[i] % 9;
int[] cands = pz.m_numbers[x, y].candidates();
pz[x+1,y+1] = cands[ro.Next(0, cands.Length - 1)];
}
str=ds.do_solve(pz.exportPuzzle(false));
if (ds.solution_count(pz.exportPuzzle(false))>0)
break;
}
pz.loadPuzzle(str.ToCharArray());
for (int i = 0; i < 81; ++i)
{
int x = remove[i] / 9 + 1 ;
int y = remove[i] % 9 + 1 ;
int num = pz[x, y];
pz[x, y] = 0;
ds.do_solve(pz.exportPuzzle(false));
if (ds.solution_count(pz.exportPuzzle(false)) != 1)
{
pz[x, y] = num;
}
}
return pz.exportPuzzle(false);
}
}
}
Codeusing 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;
private 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;
return run(str);
}
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();
}
}
}
}