主题：【支持西西河】喜欢费脑子游戏的请进 -- 大卫
家园 【支持西西河】喜欢费脑子游戏的请进 1. 九宫阵介绍：
什么是“九宫阵”？
它是一个智力游戏，已经有20 多年的历史了，是个叫Howard Garns 的1979年发明的，原名叫 number place。 1984年引入日本， 改名为"Sudoku"， 汉字为“数独”。 意思是“每个数一次”。 到今年在很多国家流行起来，特别是英国。 英国很多报刊， 大到泰晤士报， 每天一则。
九宫阵是一个9×9的方阵，由9个“九宫格”构成，每个九宫格又由3×3共9个小格子构成。游戏规则是：在每个空白小格子里面填上1-9的数字，使每个数字在每个九宫格内以及在整个“九宫阵”中每行、每列上均只出现一次。
外链图片需谨慎，可能会被源头改2. 主要解题方式：
有直观推理法和数字记录计算法两类解题方式，其中直观推理法就是不使用笔记录，单纯用经验形成的推理规则推算出空格的数字。而数字记录计算法就是根据排斥性定理计算并记录各空各的候选数，然后依据一些删除候选数的方法(删数法，相当于数学中的定理)来简化候选数，当格里的候选数满足唯一性定理时，就可确定格里应该放的数字。
两种解题方式都是建立在下面的排斥性公理和唯一性定理上。
外链图片需谨慎，可能会被源头改3. 候选数、排斥性公理和唯一性定理：
候选数定义：候选数是与空格相关的。某一个空格在某一盘面时可以填入的数字，就称为此时此格的候选数。
可以填入某一个空格的数字，一定会列于该空格的候选数中；不在候选数中的数字，就不能填入该空格中。
排斥性公理：当某一格放了某一数字后，此格所在的行及列及九宫格的其它格就不能再放置这个数字。
其实这就是九宫阵的规则了。
唯一性定理：
(a) 某一个格所在的行或列或九宫格已出现过的数字已达 8 个，那么这个格就应该填入这个还没出现过的数字。
(b) 某一个格的候选数仅有 1 个数字，则此格可以填入这个数字。
(c) 某一个格有候选数A，而其所在的行或列或九宫格的其它空格都不包含候选数A，则此格可以填入这个数字。
4. 直观推理法的具体介绍：
(a) 唯一性定理的(a)法，可以很直观地看出来。而唯一性定理的(b)、(c)法，则可以在下面其它方法做完后，再仔细计算使用。
(b) 当相邻、并成一排(列)的3个3×3九宫阵里(所以可以同时看成是相邻的3行(列))，对某一数字而言，已经在其中2个九宫阵(同时也是2行或2列里)填入了2个数字，则第3个此数字只能填在剩下的那个九宫阵里的一行(列)里。这时如果此行列只有一个空格，或者是由于其它方向的行列限制了它只能有一个格能放置此数字，则就可以确定此格放置此数字。见外链出处的第6贴。
(c) 如果一个九宫阵（3X3）里的空格（未解出数字的格）可分解为在两列(行)里，特别是其中一列(行)的空格比较少，则看看比较多的那列(行)的小方阵外面已标数字中有没有小方阵里没有的数字，如有，则可以确定此数应该填入空格少的哪列(行)的空格集里。如果这时其它方向能提供一些限制，则可能能解出格里的数字来。见上贴的第13楼。
(d) 如果一个小方阵里的空格都在一行（列）里，那么就应该知道此几个空格里应该填的数字的集合（虽然哪个空格填哪个数字还不知道）。
所以，此对应行（列）里的剩余空格就可以排除这些数字，从而有可能可以确定应该填什么。见上贴的第14楼。此方法其实就是数字记录计算法里的显式数对法。
直观推理法还有很多种具体方法，这里就不赘列了。
5. 数字记录计算法具体介绍：
(a) 显式数对、多数链删数法：
当2个候选数只出现在一行或列或九宫格的两个空格，而且此两个空格也只有此2个候选数时，则此行或列或九宫格的其它空格，就可以删除此2个候选数。上述方法称为显式数对删数法。
把上面的2个候选数两个空格推广到多个候选数多个空格，道理同样成立，叫显式多数链删数法。显式数对删数法是显式多数链删数法的一个特例。
(b) 隐式数对、多数链删数法：
当2个候选数只出现在一行或列或九宫格的两个空格(但此两个空格可以放置其它候选数)，则这两个空格，就可以删除除此2个候选数外的其它候选数。上述方法称为隐式数对删数法。
把上面的2个候选数两个空格推广到多个候选数多个空格，道理同样成立，叫隐式多数链删数法。隐式数对删数法是隐式多数链删数法的一个特例。
(c) 区域删数法：
一个3*3九宫阵可以看成3行，3列，每行列有三个格，每一个这样的行或列就称为一个区域。
一个3*3九宫阵由3个行区域，3个列区域组成，一行(列)由3个行(列)区域组成。
由此可见，一个区域所在的不光是在一个九宫阵里，同时也可能在一行或一列里。
当某一个候选数在某一行(列，九宫阵)里只出现在某一区域时，则此区域所在的其它九宫阵(列，行)里的其它空格，就可以删除此候选数。这样的方法叫区域删数法。
(d) 多链列删数法：
当某个数字在某两列(行)仅出现在相同的两行(列)时，就可以把这两行(列)其他宫格候选数中的该数字删减掉。叫矩形顶点删数法(2链列删数法)。
推广到n个数字在n列(行) 仅出现在相同的n行(列)时，道理道理同样成立，叫多链列删数法。
(e) 关键数删数法：关键数删数法比较复杂，这里就暂时不介绍了。关键数删数法，其实就是一种简化的试探搜索法，即对候选数，先假设它为格里应该填的数字，然后继续做下去，如果出现矛盾，则说明此候选数假设错了，反之则说明假设对，此格应该填此数。当然关键数删数法一次只考虑一个数，所以计算量小好多，而且也可以利用删除没有的候选数来简化。但我想在计算机里实现关键数删数法太复杂，还不如直接实现搜索法。
本帖一共被 1 帖 引用 (帖内工具实现)
