数独求解器的算法复杂度(Big-O) [英] Algorithm Complexity (Big-O) of sudoku solver

问题描述

我正在寻找如何找到它"，因为我不知道如何找到程序的算法复杂性.

I'm look for the "how do you find it" because I have no idea how to approach finding the algorithm complexity of my program.

我使用Java编写了一个sudoku求解器，但没有考虑到效率(我想尝试使其以递归方式工作，我成功了！)

I wrote a sudoku solver using java, without efficiency in mind (I wanted to try to make it work recursively, which i succeeded with!)

一些背景:

我的策略采用回溯来确定给定Sudoku拼图的拼图是否只有一种独特的解决方案.所以我基本上读了一个给定的谜题，并解决了.一旦找到一个解决方案，就不一定要做，需要继续探索进一步的解决方案.最后，发生以下三种可能的结果之一:难题根本无法解决，难题具有独特的解决方案，或者难题具有多种解决方案.

my strategy employs backtracking to determine, for a given Sudoku puzzle, whether the puzzle only has one unique solution or not. So i basically read in a given puzzle, and solve it. Once i found one solution, i'm not necessarily done, need to continue to explore for further solutions. At the end, one of three possible outcomes happens: the puzzle is not solvable at all, the puzzle has a unique solution, or the puzzle has multiple solutions.

我的程序从一个文件中读取拼图坐标，该文件的每个给定数字都有一行，由行，列和数字组成.按照我自己的约定，左上角的7表示为007.

My program reads in the puzzle coordinates from a file that has one line for each given digit, consisting of the row, column, and digit. By my own convention, the upper left square of 7 is written as 007.

实施:

我从文件中加载值，并将它们存储在二维数组中 我沿着数组向下移动，直到找到一个Blank(空值)，并将其设置为1.然后检查是否有冲突(输入的值是否有效). 如果是，我将移至下一个值. 如果否，则将值增加1，直到找到一个有效的数字为止，或者如果它们均不起作用(1到9)，则返回1步到调整后的最后一个值，然后再递增该值(使用递归) ). 当所有81个元素都填满且没有冲突时，我就解决了. 如果找到任何解决方案，我将它们打印到终端上. 否则，如果我尝试对最初修改的FIRST元素退一步"，则意味着没有解决方案.

I load the values in, from the file, and stored them in a 2-D array I go down the array until i find a Blank (unfilled value), and set it to 1. And check for any conflicts (whether the value i entered is valid or not). If yes, I move onto the next value. If no, I increment the value by 1, until I find a digit that works, or if none of them work (1 through 9), I go back 1 step to the last value that I adjusted and I increment that one (using recursion). I am done solving when all 81 elements have been filled, without conflicts. If any solutions are found, I print them to the terminal. Otherwise, if I try to "go back one step" on the FIRST element that I initially modified, it means that there were no solutions.

我的程序算法复杂度如何?我以为它可能是线性[O(n)]，但是我要多次访问该数组，所以我不确定:(

How can my programs algorithm complexity? I thought it might be linear [ O(n) ], but I am accessing the array multiple times, so i'm not sure :(

感谢您的帮助

推荐答案

O( n ^ m )其中， n 是每个正方形的可能性(即经典数独中的9个)和 m 是空白的数量.

O(n ^ m) where n is the number of possibilities for each square (i.e., 9 in classic Sudoku) and m is the number of spaces that are blank.

这可以通过仅从单个空白向后工作来看到.如果只有一个空白，那么您有 n 种可能性，在最坏的情况下必须解决.如果有两个空白，那么对于第一个空白，您必须分别对第一个空白的 n 个可能性和对第二个空白的 n 个可能性进行研究.如果有三个空格，则必须为第一个空格处理 n 个可能性.这些可能性中的每一个都会产生一个带有两个空白的谜题，其中两个空白具有 n ^ 2个可能性.

This can be seen by working backwards from only a single blank. If there is only one blank, then you have n possibilities that you must work through in the worst case. If there are two blanks, then you must work through n possibilities for the first blank and n possibilities for the second blank for each of the possibilities for the first blank. If there are three blanks, then you must work through n possibilities for the first blank. Each of those possibilities will yield a puzzle with two blanks that has n^2 possibilities.

此算法通过可能的解决方案执行深度优先搜索.图的每个级别代表单个正方形的选择.图的深度是需要填充的正方形数.在分支因子为 n 且深度为 m 的情况下，在图形中查找解决方案的最坏情况下的性能为O( n ^ m ).

This algorithm performs a depth-first search through the possible solutions. Each level of the graph represents the choices for a single square. The depth of the graph is the number of squares that need to be filled. With a branching factor of n and a depth of m, finding a solution in the graph has a worst-case performance of O(n ^ m).

这篇关于数独求解器的算法复杂度(Big-O)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！