大号波斯猫 发表于 2023-1-28 17:08:09

从零开始手搓89的数独求解程序

放假在家无聊,考虑搞一个能在计算器上用的数独求解程序。目标是把有解的数独都能至少求出一个解。
一开始建了个Java项目,因为平时工作Java用得多,比较顺手。
以此类网上常见的数独作为输入。为了调试方便,直接弄成了txt文件进行读取。



目前网上常见的数独程序采用回溯算法穷举,好处是程序编写简便,但是考虑到后期需要移植到89t上,运行内存和CPU性能都不足以支持大量穷举。因此考虑优先通过逻辑判断进行处理。判断逻辑包括行、列、宫的唯一性限制,以及部分常见的数独解题技巧,本程序添加了基本单元外排除法和余数法。
对于一部分简单的数独题,单纯通过逻辑判断就可以得出唯一解。

接下来难度升级:
我找到了所谓的“最难数独”

这个题用之前的程序已经无法解出,需要对一些格子进行多选一的尝试。
于是在接下来的部分参考了回溯算法,选定一个格子填入可能的数字,再进行求解,如果无解,就可以排除尝试的数字。
由于每个格子的候选项已经大致解除,穷举数量大幅减少,成功在400ms以内解出。

那么,还有没有更难的呢。
接下来我发现了这个。

在某数独爱好论坛上,发现了更难的题目。
基本无法靠逻辑判断和技巧填入数据,直接进入试错阶段。
在此对程序进行了亿点点调优,成功解决,需要将近1s才能解出。

至此,程序本身已经没有什么问题,接下来就是移植到计算器上,做成一个随身携带的数独“外挂”。
首先考虑的是改成python,移植到prime v2和卡西欧cg50上。
但是运行之后发现效果极差。
不知道是python效率的问题还是啥,网页游戏高级版的数独需要5~10s才能解出,论坛版的地狱难度则是直接卡死。

于是考虑改成C语言运行,装在89上。
在进行了亿点点改造之后……


内存不足,凉凉。
于是又进行了亿点点内存优化。


终于可以成功运行,至于运行速度嘛,只能说68k已经尽力了,能解出结果就是成功。


大号波斯猫 发表于 2023-1-31 22:02:45

本帖最后由 大号波斯猫 于 2023-1-31 22:05 编辑

放一个编译完的程序在这里,市面上常见的数独游戏,最高级难度一般都能在10秒以内解出。
那些需要多次试错的顶级难题耗时就比较长,最长的是上文那个“Platinum Blonde”,耗时将近20分钟。
输入的时候一次输入一整行9个数字,未知数按0。无需任何空格或逗号,输入完一行后按确认,按提示输入下一行。
全部输入完后按确认,页面展示输入结果,再次按确认开始求解。

!!!注意!!!
程序未做任何防错处理,输入不合理或中途试图强行退出会死机。抠电池可解。


farter 发表于 2023-2-7 17:15:46

数独进一步加速,在“某行列宫内还能不能填x”“某行列宫内有那些地方可以填x”“某个格子里可以填哪些x”都可以用位运算的【还有高级算法dancing links虽然内存可能不够【
近期其实在思考把迭代加深搜索算法用到数独上面(指定一个试的力度,唯一解路线一路推下去不算试,在某个层级搜了一定量后可以排除一部分候选数(虽然不一定做到了最后,只要能推导出矛盾就行),之后就不用再试了),虽然只是想法,实现可能还比较复杂(
页: [1]
查看完整版本: 从零开始手搓89的数独求解程序