数独游戏开发及唯一解算法设计

默认分类·游戏开发笔记 · 2016-08-04 · 1210 人浏览
image-20240910074306677

唯一解生成算法

数独中,有一个被称作唯一性技巧的东西,唯一性技巧基于这样一个事实——各类出版物上发布的数独题目都只有唯一解。

事实上,绝大多数数独玩家有这样的共识:即合格的数独题目解应该是唯一的。

因此,为了保证题目合格、有效,出题者在制作题目时,会将一些虽然不违反数独规则,但会导致题目出现双解或多解的特殊结构加以处理。

这也就代表我们的游戏设计中,不能出现多解

img

核心思路:回溯法+广度优先生成

目前主要的思路就是按照1-9的顺序填数,把整个大九宫格划分为9个小的小九宫格,按照1-9的顺序在每个小九宫格内随机填数,并对不需要回溯的特殊分支进行剪枝处理。

  • 比如填1的时候,先将候选数更改为“1”,然后从左上的小九宫格内填候选数,按从左至右从上至下的顺序填到最后一个小九宫格,当所有的小九宫格内都包含了候选数字“1”时,将候选数更改为2,然后重复这个过程;
  • 如果填数过程中数字在横行,纵行有重复,则重新在这个小九宫格内选取空格(由于我们是把整个大九宫格分为了9个小九宫格,然后按照小九宫格的顺序填入候选数,所以无需检测在同一小九宫格内候选数是否重复);如果这个小九宫格内没有可用空格,则回溯到上一个小九宫格,直到1-9的候选数填入完毕
  • 整个过程中数字1和9基本是不需要回溯的,并且无需检测小九宫内候选数是否重复,回溯次数可以大大减少

之前做的生成例子,没有优化 http://tieba.baidu.com/p/4555720809

img

ui设计思路

image-20240910074448839

img

img

想法是把上面三张图片的风格汇集在一起

image-20240910074602501

image-20240910074643783

成品

image-20240910074306677

Theme Jasmine by Kent Liao