基于回溯法的数独求解器事件记录与Pygame显示异常问题
问题定位与修复方案
核心异常根因
1. registre列表残留历史失败尝试的旧记录
self.registre仅在__init__阶段被初始化为空列表,整个Grid实例的生命周期内不会自动清空。
而create_grid方法是最多循环tries_max次的重试逻辑:每次尝试会走「生成随机初始盘→复制工作网格→调用solver求解」的流程,只要本次尝试失败(初始化超时、求解超时、未得到合法解),就直接continue进入下一次循环,全程没有清空registre的操作。
这意味着前N次失败尝试中solver追加的所有操作记录,都会永久保留在registre列表中。当某一次尝试最终求解成功时:
- 每次尝试都会重新赋值
self.grid0、self.grid,最后一次成功的赋值会覆盖旧值,因此打印出来的初始网格、最终求解网格完全正确; - 但
registre的前半段全是之前失败尝试留下的、和当前网格完全无关的旧操作记录。
这直接对应你观察到的现象:比如示例1的初始网格中(0,1)位置是预填的固定数字8,solver逻辑根本不会触碰这个非零格子,但registre中却出现了多条针对(0,1)的赋值、清0记录——这些记录根本不属于本次求解流程,是之前某次网格状态完全不同的失败尝试的残留。
同理,Pygame显示层按顺序读取registre时,一上来就加载了一堆位置不匹配的旧操作,自然会出现数字重叠、格子空白的问题。
2. 求解成功后的回溯退栈逻辑会污染最终状态
当前solver的逻辑存在流程漏洞:当递归调用检测到整个网格已经填满合法数字(即求解成功)时,break仅能跳出当前的数值遍历循环,但执行流还是会顺序走到后面的退栈逻辑:
self.registre.append([0,i,j]) self.grid[i][j]=0
也就是说,哪怕已经找到了正确解,退栈过程中还是会无差别把已经填好的合法数字重新清0、追加清0的记录,既会干扰显示层的时序,严重时甚至会把最终正确的网格改回带空位的状态。
修复步骤
- 把
registre的清空逻辑移到每次单次求解尝试的最开头:在create_grid的循环内、调用initialize_board和solver之前,执行self.registre.clear(),保证每次求解积累的记录完全对应本次的网格状态,没有历史残留。 - 在类的初始化中增加全局求解状态标记
self.solved = False:当某次递归检测到网格中没有剩余空位时,将self.solved设为True,立刻逐层返回,不再执行后续的遍历、赋值、记录追加操作。 - 给所有退栈操作加上状态判断:只有当
self.solved == False时,才执行追加清0记录、把格子重置为0的逻辑,避免污染已经得到的正确解。
内容的提问来源于stack exchange,提问作者user14434207
相关产品推荐
相关产品推荐

