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

大号波斯猫

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



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

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

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

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

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

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

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


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


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

大号波斯猫

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

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


soduku.89z (4.33 KB, 下载次数: 16)

2023-1-31 22:00 上传

点击文件名下载附件

farter

数独进一步加速，在“某行列宫内还能不能填x”“某行列宫内有那些地方可以填x”“某个格子里可以填哪些x”都可以用位运算的【还有高级算法dancing links虽然内存可能不够【
近期其实在思考把迭代加深搜索算法用到数独上面（指定一个试的力度，唯一解路线一路推下去不算试，在某个层级搜了一定量后可以排除一部分候选数（虽然不一定做到了最后，只要能推导出矛盾就行），之后就不用再试了），虽然只是想法，实现可能还比较复杂（