唯一解生成算法
数独中,有一个被称作唯一性技巧的东西,唯一性技巧基于这样一个事实——各类出版物上发布的数独题目都只有唯一解。
事实上,绝大多数数独玩家有这样的共识:即合格的数独题目解应该是唯一的。
因此,为了保证题目合格、有效,出题者在制作题目时,会将一些虽然不违反数独规则,但会导致题目出现双解或多解的特殊结构加以处理。
这也就代表我们的游戏设计中,不能出现多解
核心思路:回溯法+广度优先生成
目前主要的思路就是按照1-9的顺序填数,把整个大九宫格划分为9个小的小九宫格,按照1-9的顺序在每个小九宫格内随机填数,并对不需要回溯的特殊分支进行剪枝处理。
- 比如填1的时候,先将候选数更改为“1”,然后从左上的小九宫格内填候选数,按从左至右从上至下的顺序填到最后一个小九宫格,当所有的小九宫格内都包含了候选数字“1”时,将候选数更改为2,然后重复这个过程;
- 如果填数过程中数字在横行,纵行有重复,则重新在这个小九宫格内选取空格(由于我们是把整个大九宫格分为了9个小九宫格,然后按照小九宫格的顺序填入候选数,所以无需检测在同一小九宫格内候选数是否重复);如果这个小九宫格内没有可用空格,则回溯到上一个小九宫格,直到1-9的候选数填入完毕
- 整个过程中数字1和9基本是不需要回溯的,并且无需检测小九宫内候选数是否重复,回溯次数可以大大减少
之前做的生成例子,没有优化 http://tieba.baidu.com/p/4555720809
ui设计思路
想法是把上面三张图片的风格汇集在一起