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