Algorithm Complexity (Big-O) of sudoku solver

Question

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!)

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.

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.

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 :(

Any help is appreciated

Solution 1

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.

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.

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).

Solution 2

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?

Where in the first line can the number 2 go?

...

Where in the last line can the number 9 go?

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?

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.

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

Comments

[cozos]

Wouldn't you only need to work through n-1 possibilities for the second blank, n-2 possibilities for the third blank, etc, since in Sudoku you can only use a number once?

[mpen]

If there's exactly 1 blank, then there's only 1 possibility -- the missing number. Well... I mean I guess you have to check the rows and cols to rule the other (n-1=8) numbers out, which takes O(n) time, but those don't cause recursion.

[Gregory Morse]

This would be a worst case for the most naïve algorithm. If any sort of rule based elimination is used whatsoever, O(n^m) would be replaced by a much smaller number for m than e.g. n^2. In fact a 9x9 Sodoku which already has certain squares filled in could probably be solved using a brute-force rule-pruned algorithm in very fast time. Of course its non-linear and NP-complete and there are methods to solve it from that perspective as well.

[Gregory Morse]

It transforms an NP-complete problem so there will always be exponential growth as long as its not a trivial sudoku. Unless P=NP which isn't likely...