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