算法之SudokuPlus(数独,又称九宫)系列 --- 迷题生成篇(1)

二, 九宫之简化篇

解法是有了, 可题目是从那里来的呢? 难道是随手填出来的? 1, 2, 3, 4 ... (九宫题目自定义中...) 啊?!!真的出现了一个! (在这里我们称之为完整九宫) ^_^, 这个九宫, 还真有规律啊...(别忘了, Ctrl + S和F4... 郁闷, 竟然又发现了个BUG, 读取完整九宫的时候竟然会出错. 这错犯得...)


貌似, 貌似这个是答案啊. 怎么给人出个题目呢? 我东删删, 西减减, 还真有点模样了...
(九宫单机版-->编辑-->更高难度)



那用程序该怎么实现呢? 

步骤1: 我们把一个完整九宫看做一个九宫题目. 显然, 这个题目有唯一解. (原因嘛, 天知地知, 你知我知)

步骤2: 从得到的九宫题目里, 任选一个数, 移除, 看得到的新九宫题目是否有解. 若有唯一解, 则保留所得九宫题目; 若无解或多解(^_^既然是从完整九宫拿到的, 当然没有无解的情况了), 则将移除的数填回.

步骤3: 重复步骤2直到没有数可以再被移除或者达到一定的条件(由你说的算, 比如最终所得九宫题目所填入数的多少)为止.


^_^想想看, 貌似这3个步骤有很多可以利用的地方呢...

Q1: 如果步骤3里的结束条件是由我们确定的, 那么我们是不是可以控制难度(九宫题目初始时所填入数的多少)呢? --- 所得题目难度的实现

Q2: 如果步骤2中移除数字时考虑相关数字的移除, 我们是不是还可以控制所得九宫题目的"形状"呢? --- 特殊格式的得到

(1)中心对称(设置-->新建选项-->中心对称)	(2)左右对称
(3)上下对称	(4)全对称(中心, 左右, 上下均对称)
(5)半一致(我报[MyPaper]上用的) (格式第1, 3, 5, 7, 9个大宫格形状一样, 2, 4, 6, 8一样)	(6)全一致

Q3: 如果步骤1中起始的不是一个完整九宫题目, 而是一个从报纸上得到的九宫题目, 那利用步骤2, 步骤3是不是可以得到一种更难的版本呢? --- 更难版本的获得

等等等等, 完整题目怎么能这么得到?! 那就看下篇 --- 随机题目的生成
^_^好像不对, 下篇是 --- 九宫题目有多少

注: 关于标题中的简化2字, 指的是数的个数多少的简化

(九宫蓝牙对战版前几天基本完工了, Project的report也该写了. ^_^, 决定了, 让他们去写, 哈哈哈哈哈哈)

算法之SudokuPlus(数独,又称九宫)系列 --- 解法篇

--- SudokuPlus, 数独, 又称九宫. 就是在9X9的格子上填入1-9的数字, 使得每一行,每一列, 每一个大宫格(3X3)都是1-9的不同组合.

这个游戏, 是today和我报必有的部分, 想必大家好多都看到过, 也玩过. 

大四上学期的时候, 收到身在澳大利亚的小师姐的求助信. 好像她们当时的作业就是写得相关的东西, 不过后来看来要简单的多. 可能当时玩游戏太投入吧, 也没把那封信当回事, 直到现在都觉得过意不去. 然后就把这件事情逐渐抛诸脑后, 也不曾想有一天会再度想起.

1年多前大学毕业, 正是这个游戏流行正盛的时候, 偶然在today上看过, 工作无聊之余竟然逐渐感兴趣了起来. 那时候住的地方离公司很远, 又有同样对这类问题较感兴趣的jason同行, 于是在地铁上的时候经常聊起这个话题. 加之工作空闲乏味, 于是就一时兴起, 写了"九宫手机版", "九宫PC单机版", 乃至后来的"九宫PC网络版". 从开始的无界面, 到最后的使用MFC的自画界面, 也算是"历经沧桑". 唉, 也是在很久很久后的一天, 大概是PC单机版写到1.0版的时候, 突然记起了小师姐求助那件事, 发掘N久以前的Email后才发现: 我那时的兴趣, 竟然是倒推一年的题目...

现在, 在沉寂一年之后, 竟有了想把一些算法和程序整理一下的冲动.

(注: 由于不曾在网络上搜索过类似的算法, so可能坐井观天...)

一, 九宫之解法篇

步骤1: 对每一个小格, 检查所在行, 列, 大宫格里1-9填入的情况, 若只存在一种数未被填 入, 则填入. 
例如: 如图在第2行, 第4列的位置只有9未被填入, 因此在那个位置填入9.


步骤2: 对每一行, 每一列和每一个大宫格里的每一个数进行检查, 看是否存在某个数只能在其中的唯一位置填入, 若存在, 则填入.
例如: 如图, 检查第二行的1时发现, 它只可以填入到最右边的位置, 于是填入.
  
(最后一副图画的横线是常用来目测答案的方法)

步骤3: 重复步骤1-2 直到没有数字可以填入为止.

步骤4: 检查得到的答案是否完整. 若完整, 则结束. 若不完整, 则用穷举法找到答案.

注: 现在所有流行的九宫游戏都是有唯一解的. (因为有多解的问题实在没多大意义) 

注: 对于只有唯一解的九宫问题来说, 还从来出现过没有步骤3结束时没有解开的题目. 所以在我的程序里, 也就没有用穷举法. (如果你遇到那个程序解不开的问题, 而你有确认那个问题答案是唯一的, 请告诉我)

当然, 其实用来判断一个数是否要填入某个位置的方法还有更多, 只不过已经没有开发的必要...