终端数独游戏

写这个小游戏是因为在leetcode做题的时候, 遇到了37. 解数独这个题, 做完便想到可以将其扩展为一个小游戏.

项目地址: https://github.com/caibingcheng/sudoku

编译 & 运行

支持Windows和Linux平台.

1

g++ ./main.cpp -o sudoku && ./sudoku

操作

• 移动: w/a/s/d
• 填写: 1-9, .表示留空
• 重置: r
• 新游戏: n, 生成同等难度的新游戏
• 检查: c, 检查所有所填项是否可以解决该题
• 提示: h, 提示当前空格可以填入的候选项, 该候选项不保证可解
• 更换难度: -/=, -表示降低难度, =表示提高难度, 难度等级1-7
• 退出: q

生成方法

• 生成一个9x9宫格
• 随机的11个位置填入随机的数字(有人证明说11个数有解的概率最大)
• 解该数独(回溯/DFS)
• 对解完的数独擦除若干个数字, 最后结果就是题目

已知问题

不保证唯一解

以上生成方法不保证唯一解, 如果需要唯一解, 可以在擦除数字的时候, 每擦除一个, 判断新题的解的个数, 但是这样时间太久了. 有查到DLX算法, 但是暂不计划花时间去看.

偶现生成时间很久

主要耗时部分:

1. 生成数独过程中的解数独部分, 解的位置离起始位置可能很远
2. 没有保证随机11数之后的数独一定可解, 因此可能导致遍历完整个解空间

可以通过设置最大查询深度来解决这个问题, 如果一定深度后还没有找到解, 则重新执行生成步骤. 但是最大深度如何设置合理? 还没有去研究.