Applications in Artificial Intelligence

Sudoku Solver-Depth First Search Algorithm page 4

Recursive programming is highly suggested for the implementation of the solution, In my case I did not use it.

I used arrays  and ordinary programming techniques. My solver was written in Visual Basic 6.0.

The programming language is important butwhat is more important is the algorithm to solve the puzzle.

So far, my solver is able to solve 5 stars puzzles in less than 5 minutes. For  Sudoku's above 5 stars the solver took more than 3 hours in worse cases, more than 90,000,000 iterations average to find the solution.

The puzzle I used as example was published on Wikipedia as the one of the most difficult puzzles and it took 19,343,346  iterations and aprox. 1 hour to my solver to find the solution.

Figure above shows  the graph of some of the puzzles solved by my program (Y axis: number of iterations, X axis: number of empty squares) . The graph above illustrates 22 puzzles solved with my application. These puzzles were posted on internet as the most difficult sudoku puzzles. The worst case is the puzzle that took 99,771,728 iterations and almost 6 hours to find the solution.

So far, my solver has been able to solve every single Sudoku puzzle.

 There are 6670903752021072936960 or 6.7×1021 Sudoku grids (Bertram Felgenhauer and Frazer Jarvis)