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

If you're using backtracking, your complexity is probably exponential-ish. I.e. for every move taken, you recurse into more or less every other possible move. — millimoose
Could you post your code? Or just the relevant sections of it? — Daniel Williams

Matthew T. Staebler Matthew T. Staebler · Accepted Answer · 2013-03-10T21:02:49

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

Algorithm Complexity (Big-O) of sudoku solver

2 Answers