Applications in Artificial Intelligence

Sudoku Solver-Depth First Search Algorithm page 3

 If we need to transform the problem ofsolving a Sudoku puzzle to a “solution tree” problem the following approach can be taken in consideration to implement a computer program capable to solve the puzzle (see illustration above):

a)load  the original puzzle (only givens)from a file

b)determine which are the valid candidates per empty cell and load the valid candidatesinto an array along with givens.

c)create the table of  the valid candidates of empty cells in ascendant order fromless to more valid candidates.

d)apply DFS to the table of candidates created on the previous step.

e) Once applied DFS, a solution should be obtained, otherwise there is an inconsistency  in the original  puzzle.