Applications in Artificial Intelligence

Sudoku Solver-Depth First Search Algorithm page 1

Solution trees can help us to visualize the structure of any given the problem (See figure above). Also Solution trees can help us understand how these types of algorithms really work.

It starts at the top of the three and goes tot he bottom branch by branch, leave by leave in order to find the first solution. What Is the Depth First Search algorithm? choose one unfilled square and consider all its possible values. One at a time, try assigning the square each value, and searching from the resulting position. In other words, we search for a value such that we can successfully search for a solution from the result of assigning a square to this value. If the search leads to an failed position, go back and consider another value. This is a recursive search, and we call it a depth-first search because we (recursively) consider all possibilities or values before we consider a different value. If we transform the problem of solving the puzzle into a “solution tree”, we might find that we have a three of nth levels as much empty square we need to solve. For each level we might have as many “branches” as candidates for such empty square. In these context, figure shows the solution tree for a Sudoku puzzle with 64 empty squares, the value on the right for each level, represents the location of the equivalent square.This type of solution trees is well used when a solution for a problem needs to be found based on limited values.