cnCalc计算器论坛

 找回密码
 注册
搜索
查看: 2231|回复: 2

[89/92/V200] 从零开始手搓89的数独求解程序

[复制链接]
发表于 2023-1-28 17:08:09 | 显示全部楼层 |阅读模式
放假在家无聊,考虑搞一个能在计算器上用的数独求解程序。目标是把有解的数独都能至少求出一个解。
一开始建了个Java项目,因为平时工作Java用得多,比较顺手。
以此类网上常见的数独作为输入。为了调试方便,直接弄成了txt文件进行读取。

1.PNG

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

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

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

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

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

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

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


评分

参与人数 2金钱 +2 收起 理由
escape + 1 666
zyf722 + 1 赞一个!

查看全部评分

 楼主| 发表于 2023-1-31 22:02:45 | 显示全部楼层
本帖最后由 大号波斯猫 于 2023-1-31 22:05 编辑

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

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


soduku.89z (4.33 KB, 下载次数: 15)
发表于 2023-2-7 17:15:46 | 显示全部楼层
数独进一步加速,在“某行列宫内还能不能填x”“某行列宫内有那些地方可以填x”“某个格子里可以填哪些x”都可以用位运算的【还有高级算法dancing links虽然内存可能不够【
近期其实在思考把迭代加深搜索算法用到数独上面(指定一个试的力度,唯一解路线一路推下去不算试,在某个层级搜了一定量后可以排除一部分候选数(虽然不一定做到了最后,只要能推导出矛盾就行),之后就不用再试了),虽然只是想法,实现可能还比较复杂(
您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|cnCalc计算器论坛

GMT+8, 2024-11-1 06:55 , Processed in 0.132792 second(s), 23 queries .

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表