--- 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时发现, 它只可以填入到最右边的位置, 于是填入.
(最后一副图画的横线是常用来目测答案的方法)
这个游戏, 是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结束时没有解开的题目. 所以在我的程序里, 也就没有用穷举法. (如果你遇到那个程序解不开的问题, 而你有确认那个问题答案是唯一的, 请告诉我)
当然, 其实用来判断一个数是否要填入某个位置的方法还有更多, 只不过已经没有开发的必要...
No comments:
Post a Comment