我用java编写了一个数独求解器,没有效率(我想尝试让它递归工作,我成功了！)
一些背景：
我的策略采用回溯来确定,对于给定的数独谜题,谜题是否只有一个独特的解决方案.所以我基本上阅读了一个给定的谜题并解决它.一旦我找到了一个解决方案,我不一定完成,需要继续探索进一步的解决方案.最后,三种可能的结果之一发生：难题根本无法解决,拼图有独特的解决方案,或者拼图有多种解决方案.
我的程序从一个文件中读取拼图坐标,该文件对于每个给定的数字有一行,包括行,列和数字.根据我自己的惯例,7的左上角正方形写为007.
执行：
我从文件中加载值,并将它们存储在二维数组中
我按下数组,直到找到空白(未填充的值),并将其设置为1.并检查是否有任何冲突(我输入的值是否有效).
如果是,我转到下一个值.
如果不是,我将值递增1,直到找到一个有效的数字,或者如果它们都不起作用(1到9),我返回1步到我调整的最后一个值,然后递增该值(使用递归) ).
当所有81个元素都被填满时,我完成了解决,没有冲突.
如果找到任何解决方案,我将它们打印到终端.
否则,如果我尝试在我最初修改的FIRST元素上“返回一步”,则意味着没有解决方案.
我的程序如何算法复杂度？我认为它可能是线性的[O(n)],但我多次访问该数组,所以我不确定:(
任何帮助表示赞赏
解决方法
这可以通过仅从一个空白向后工作来看出.如果只有一个空白,那么你有可能在最坏的情况下必须完成.如果有两个空白,则必须为第一个空白处理n种可能性,对于第一个空白的每种可能性,必须为第二个空白处理n种可能性.如果有三个空白,那么你必须为第一个空白处理n种可能性.这些可能性中的每一种都将产生具有两个空白的拼图,其具有n ^ 2种可能性.
该算法通过可能的解决方案执行深度优先搜索.图表的每个级别代表单个正方形的选择.图表的深度是需要填充的正方形的数量.在分支因子为n且深度为m的情况下,在图中找到解决方案具有O(n ^ m)的最差情况性能.
