java 数独求解器的算法复杂性（Big-O）

Algorithm Complexity (Big-O) of sudoku solver

提问by Eric Muller

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.

我正在寻找“你如何找到它”，因为我不知道如何找到我的程序的算法复杂性。

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

我用 java 写了一个数独求解器，没有考虑效率（我想尝试让它递归工作，我成功了！）

Some background:

一些背景：

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.

我的策略采用回溯法来确定，对于给定的数独谜题，该谜题是否只有一个唯一的解决方案。所以我基本上阅读了一个给定的谜题，并解决了它。一旦我找到了一个解决方案，我不一定就完成了，需要继续探索进一步的解决方案。最后，会出现三种可能的结果之一：谜题根本无法解决，谜题有唯一的解决方案，或者谜题有多个解决方案。

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.

我的程序从一个文件中读取拼图坐标，每个给定的数字都有一行，由行、列和数字组成。按照我自己的习惯，左上角的 7 写成 007。

Implementation:

执行：

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.

我从文件中加载值，并将它们存储在一个二维数组中我沿着数组向下移动，直到找到一个空白（未填充的值），并将其设置为 1。并检查是否存在任何冲突（值是否与输入是否有效）。如果是，我将转到下一个值。如果不是，我将值增加 1，直到我找到一个有效的数字，或者如果它们都无效（1 到 9），我将返回 1 步到我调整的最后一个值并增加那个值（使用递归）。当所有 81 个元素都被填满时，我就完成了解决，没有冲突。如果找到任何解决方案，我会将它们打印到终端。否则，如果我尝试在我最初修改的第一个元素上“后退一步”，则意味着没有解决方案。

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)]，但我多次访问该数组，所以我不确定:(

Any help is appreciated

任何帮助表示赞赏

回答by Matthew T. Staebler

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

O( n^ m) 其中n是每个方格的可能性数（即经典数独中的 9），m是空白的空格数。

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

这可以通过仅从单个空白向后工作来看到。如果只有一个空白，那么在最坏的情况下，您必须处理n 种可能性。如果有两个空格，则必须通过工作ñ可能性的第一个空白和ñ可能性，用于对每个第一个空白准备第二空白。如果有三个空格，那么您必须为第一个空格处理n 种可能性。这些可能性中的每一个都会产生一个有n^2 种可能性的两个空白的谜题。

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 nand a depth of m, finding a solution in the graph has a worst-case performance of O(n^ m).

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

回答by gnasher729

In many Sudokus, there will be a few numbers that can be placed directly with a bit of thought. By placing a number in the first empty cell, you give up on a lot of opportunities to reduce the possibilities. If the first ten empty cells have lots of possibilities, you get exponential growth. I'd ask the questions:

在很多数独中，都会有几个数字，稍加思索就可以直接放置。通过在第一个空单元格中放置一个数字，您会放弃很多减少可能性的机会。如果前十个空单元格有很多可能性，您将获得指数增长。我会问以下问题：

Where in the first line can the number 1 go?

第一行的数字 1 可以去哪里？

Where in the first line can the number 2 go?

数字 2 在第一行的哪个位置？

...

...

Where in the last line can the number 9 go?

最后一行中的数字 9 可以去哪里？

Same but with nine columns?

相同但有九列？

Same but with the nine boxes?

一样，但九个盒子？

Which number can go into the first cell?

哪个数字可以进入第一个单元格？

Which number can go into the 81st cell?

哪个数字可以进入第 81 个单元格？

That's 324 questions. If any question has exactly one answer, you pick that answer. If any question has no answer at all, you backtrack. If every question has two or more answers, you pick a question with the minimal number of answers.

这是 324 个问题。如果任何问题只有一个答案，您就选择那个答案。如果任何问题根本没有答案，你就回溯。如果每个问题都有两个或更多答案，则您选择一个答案数量最少的问题。

You mayget exponential growth, but only for problems that are really hard.

您可能会获得指数增长，但仅限于非常困难的问题。