先解释一下何谓最毒数独。

这是我对最难数独的称呼。之所以称之为最毒，查实乃是受站长的文章影响。记得他在站内某文章中曾用“五毒俱全”来形容量子力学中那些个物理体系的，因其“毒”就毒在体系内什么制约的物理量都无法准确确定。

大家应该知道，一个数独，如果它提供的原始确定数字越多就越容易解，相反那些制约的数字提供得越少就越难，当然少也不能少到让这数独多于一个正解。我找到的这个号称世界上最难的数独，一个最常见的那种九宫格的数独，数了数，只有21个原始数字，大概是我见过的提供最少原始数字的数独了。（不知有没有人证明过设计一个只有一个正解的九宫格数独最少不能少于多少个原始数字？）

解数独本来也不是什么超高深的智力游戏。不过我一试这个数独才知道后悔，它实在太TMD TNND难了。之前我还没遇过一个数独要花费超过一个小时去解的，也没遇见过一个数独是开始时连一个肯定数字都填不下的。而这个最毒数独我花了好几个小时才可以肯定地填下第一个数字。

这简直就是一个挑战人忍耐极限的SM游戏，不过既然开了个头，欲罢不能，当我最后找到答案时，一揽众山小，对数独这玩意儿从此感到索然无味。我发誓以后再也不沾此“毒”，不管它毒性强弱。

对“毒瘾”有兴趣的茶友，Google一下“toughest sudoku”便可找到此数独。介绍中有这么一段话：“The Everest of numerical games was published by Arto Inkala, a Finnish mathematician, on his website and is specifically designed to be unsolvable to all but the sharpest minds. ”

我数了下，有23个原始数字。

http://mathworld.wolfram.com/Sudoku.html

只有17个格子填有数字，仍然有且仅有一解。

呵呵，我倒是没中过数独的“毒”，但不幸的是，手机上的扑克牌游戏“毒”性也不小，浪费了我一些时间……

数独中保证有唯一解的最少原始数字的数目应该是像魔方的上帝之数那样可以证明的吧？

http://en.wikipedia.org/wiki/Mathematics_of_Sudoku

A paper by Gary McGuire, Bastian Tugemann, and Gilles Civario, released on 1 January 2012 proved through exhaustive computer search that the minimum number of givens is 17 in general Sudoku.

：我数了下，有23个原始数字。

我再数了数，哎，确实是23个原始数字...如果是用九进制去数的话。
喝高了。 ：-）

宇澄兄在“戒毒”前怎么也得做出一个17个数字的数独才行啊……

通常人犯傻都会一犯就犯俩，比如说去澳门搏杀输得一干二净后找大耳窿，又或者说嫁了个吸毒的把家产败得千干万净后一咬牙跺脚干脆你吸我也吸。

我也不能免俗。用手工碰完这个最毒数独后又接着犯傻想试一下自己电脑编程来解决数独，一了百了。

坦白说，如果编一个程来设计数独，那可能是一个挺高深的智力挑战，但遍一个程来解数独题，挑战性应该不算怎的。何况我采用的是最不用动脑子，光叫电脑死算的那种Brute force算法，即是将所有的数字排列组合都试一趟，看其中哪个适合。

打个比方，走迷宫，如果这迷宫只有一个进口一个出口（大概相当于只有单解的数独吧），那么我即便是一个瞎子，完全不辨方向，明知死胡同也往里面撞，只要用一只手扶着墙不断地往前走，就必定能走到出口。

Windows编程，我挑了用VC。(我认为乐于用VC的人在SM游戏中大多是M的角色。不知道用PROLOG这类语言来写是否效果更佳。)I/O那些trivial的部分不说了。算法方面我先想了想，应该写个堆栈，即等于走迷宫碰上死胡同知道退回到什么位置。然后那个判定死胡同也即每一个新填进去的数字有没有相冲突的程序核心部分用一个Function去实现，再用递归法去Call这个Function。

程序写好，调试，Debug，完后先找了一个普通的数独去做例子作测试。

原始数字输入，一Click “Run”，BINGO！正确答案立即便弹了出来， in no time。讲Crunching Number的速度，电脑自然比人脑强千百倍。

我接着再将那最毒数独的数据输入，一Click “Run”：

C R A P S !!

连电脑也被毒瘫了。一查，原来这毒数独将我的递归Function套了几千重都没递出来，Heap 部分不堪重负给压垮了。

我原先喜欢用递归写程式是因为它看上去够简洁，无奈只好弃用递归改用 while loop。

再次按“Run”，大约过了二十秒，终于有结果出来了，和手工算的答案完全一致。

查了一下， while loop循环了1897848次。

检验了一下我的程序，它的运算速度是O(n^6)，即，如果是九宫格的话，n=9。

我写这个Program尽量Soft code，理论上也可以用它来解16x16，25x25这些数独的。但算了一下O(n^6)会让16x16的耗时成30倍的增长，25x25就更不用提了。

最后再说一说，按上面rainbow茶友提供的最少原始数字数独线索，加上昌海兄加贴之诱惑，我便再破戒一次手试了一下某个具最少原始数字17个的数独。其实想想为了做研究而沾毒也不能说破戒，据说弗洛伊德跟女秘做爱大打SM是为了做心理学研究，也不算破戒嘛。总之，我发现这数独对于人脑来说并不太难，很好入口。看似砒霜，实际是大肉。但是如果让电脑来解，则耗时更多，超过一分钟才弹出答案， while loop循环了7228685次！

弗洛伊德的那个据说是记错了吧？应该是行为主义一派心理学家华生的故事。

：弗洛伊德的那个据说是记错了吧？应该是行为主义一派心理学家华生的故事。

道听途说得来，确实没仔细考证过。如果是我搞错了，向老弗爷赔个不是。

R5L6一眼看上去就是3嘛。。。。怎么会花几个小时都填不下一个数字

我是个数独爱好者，90%的业余时间我都在手机上玩这个游戏。
钻研了各种数独的解法（非数学角度），比如说unique rectangle，swordfish
后来发现这些解法让娱乐性和思考性大大降低了，还不如make guesss来得有趣
于是最终回到我自己的解法

我觉得楼主可能是从不玩数独的人呢，基本规律都没掌握，说句得罪了的话

回Seraph，我虽玩过不少数独，但解法倒真是没怎么总结过。

恕小弟后知后觉，未知如你所言之“R5L6一眼看上去就是3嘛”指的是那一格？

张贴的目的正是为了抛砖引玉。如果Seraph君对这号称世界最难的数独都觉得轻而易举等闲视之，必有解数独的优异思维方式或秘笈心得，何妨再多展露一二。

一醉和Seraph，对不起，我估计可能由于你们用google搜出来的那个数独并非我所指的那个数独，以致误会产生。

我用google.com搜“Toughest sudoku”，得出来的前两个结果一个是news.yahoo.com，一个是
www.telegraph.co.uk，打开这两个网页所看到的都是那个货真价实的最难数独。而排列第三的那个搜索结果，即
http://www.foxnews.com/tech/2010/08/19/crack-worlds-toughest-sudoku/
其所载数独根本就不是那个最难数独。它确实是有23个原始数字，再看看它Row5，Column6（上至下左至右1-9那样数）那个位置，又确实是应该填一个3。

顺便骂一下FOXNEWS，一如邓文迪她老公媒堕掌握的那些舆论工具，误导人家不是头一回了。

我干脆就将这个最难数独列在这里吧（数字0代表原来的空格），以正视听：

用Plain text再贴一次这个数独，怕上面的图形被卡。

8 0 0 0 0 0 0 0 0
0 0 3 6 0 0 0 0 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
0 0 0 0 4 5 7 0 0
0 0 0 1 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
0 9 0 0 0 0 4 0 0

几位数毒高手的切磋令我等打酱油的高山仰止！

再试了一下www.google.cn，被导向www.google.com.hk，然后搜“Toughest sudoku”，结果确实不是我最初所指的那个最毒数独。不解。为中国内地的朋友被误导致歉。

：几位数毒高手的切磋令我等打酱油的高山仰止！

如果昌海兄所指的高手小弟也有幸忝列于内，那我的武功修为也仅是拈花指 (第八重)嘛。昌海兄的武功才深不可测不告人呢。

当初染上数独之毒其滥觞也许自昌海兄在茶室里讨论“约束之美”始，我将这数独也理解成“束度” -- 几个数字零星散布于整列整行的空格中，看似可让你在空格里自由地填上数字，但其实在一定的自由度之下隐藏着约束。

你的程序写的肯定有问题，递归的话只有81层，c语言的堆栈不可能溢出的。我试着写了一下，最难数毒几乎事take no time.

#include <iostream>
#include <cstring>
class Set {
public:
Set() { std::memset(s, 0, sizeof(s)); }
bool isSet(int i, int x) const { return s[i] & (1 << x); }
bool set(int i, int x) { return s[i] |= (1 << x); }
bool clear(int i, int x) { return s[i] &= ~(1 << x); }
private:
unsigned short s[9];
};

class Checker {
public:
bool set(int i, int j, int x) {
int bi = i / 3 * 3 + j / 3;
if (r.isSet(i, x)) return false;
if (c.isSet(j, x)) return false;
if (b.isSet(bi, x)) return false;
r.set(i, x);
c.set(j, x);
b.set(bi, x);
return true;
}

void clear(int i, int j, int x) {
int bi = i / 3 * 3 + j / 3;
r.clear(i, x);
c.clear(j, x);
b.clear(bi, x);
}
private:
Set r, c, b;
};

class Solver {
public:
Solver() {
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
char x;
std::cin >> x;
data[i][j] = x - '0';
if (data[i][j]) checker.set(i, j, data[i][j]);
}
}
}

void solve() { print(); solve(0); }

private:
Checker checker;
char data[9][9];

void print() {
std::cout<<"==================\n";
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
std::cout << static_cast<int>(data[i][j]) << ' ';
}
std::cout << '\n';
}
}

void solve(int ind) {
if (ind == 81) {
print();
return;
}
int i = ind / 9, j = ind % 9;
if (!data[i][j]) {
for (int x = 1; x <=9; ++x) {
if ( ! checker.set(i, j, x) ) continue;
data[i][j] = x;

solve(ind + 1);

data[i][j] = 0;
checker.clear(i, j, x);
}
} else {
solve(ind + 1);
}
}
};

int main() {
Solver s;
s.solve();
}

果然误会了。既然楼主贴出了，何妨一试。试过再来通报。不过说到误导，，应该是楼主和一醉的对话才是真凶

impig上面的编程确实非常精妙高效，佩服。

我查了一下我原来的程序，主要问题在一是递归的Function里多用了一个for loop累赘，另一个是没有利用Bitwise Operation来储存和比较数字，故此既浪费空间又拉慢了速度，总而言之就是写得很业余吧。

我玩数独有四年了，不过还是很业余级，技术有待提高。

见到大家讨论起数独来，介绍大家玩玩这个数独网站 http://www.sudokufans.org.cn/ 许多国内知名高手都在其中呢。

呵呵，finally，俺这打酱油的遭同事引诱，用javascript（同事指定的语言）编了一个解毒程序，虽不能与C程序比速度，解出宇澄兄的毒物却也只需0.3秒：

812753649
943682175
675491283
154237896
369845721
287169534
521974368
438526917
796318452

但愿没有理解错规则：每行、每列、9个3x3方块中的每个都包含1-9各一次。晚些时候我把程序加个GUI添到主页上供偷懒用（好久没增添跟编程有关的东西了）。