# Search Spaces

Sometimes we have a problem that may consist of many different states. We may want to find a particular state of the problem which we'll call the *goal*. Consider Sudoku puzzles. A Sudoku puzzle has a state, reflecting how much of it we have solved. We are seeking a goal which is the solution of the puzzle. We could randomly try a value in a cell of the puzzle and try to solve the puzzle after having made that guess. The guess would lead to a new state of the puzzle. But, if the guess were wrong we may have to go back and undo our guess. A wrong guess could lead to a dead end. This process of guessing, trying to finish the puzzle, and undoing bad guesses is called *depth first search*. Looking for a goal by making guesses is called a depth first search of a problem space. When a dead end is found we may have to *backtrack*. Backtracking involves undoing bad guesses and then trying the next guess to see if the problem can be solved by making the new guess. The description here leads to the depth first search algorithm in Sect. 12.2.1.

## Depth-First Search Algorithm

1 **def** dfs(current, goal):

2 **if** current == goal:

3 **return** [current]

4

5 **for** next **in** adjacent(current):

6 result = dfs(next)

7 **if** result != None:

8 **return** [current] + result

9

10 **return** None

The depth first search algorithm may be written recursively. In this code the depth first search algorithm returns the path from the current node to the goal node. The backtracking occurs if the for loop completes without finding an appropriate adjacent node. In that case, *None* is returned and the previous recursive call of *dfs* goes on to the next adjacent node to look for the goal on that path.

In the last chapter an algorithm was presented for solving Sudoku puzzles that works for many puzzles, but not all. In these cases, depth first search can be applied to the puzzle *after* reducing the problem as far as possible. It is important to first apply the rules of the last chapter to reduce the puzzle because otherwise the search space is too big to search in a reasonable amount of time. The solve function in Sect. 6.6.2 includes a depth first search that will solve any Sudoku puzzle assuming that the reduce function applies the rules of the last chapter to all the groups within a puzzle. The *copy* module must be imported for this code to run correctly.

## Sudoku Depth-First Search

1 **def** solutionViable(matrix):

2 *# Check that no set is empty*

3 **for** i **in** range(9):

4 **for** j **in** range(9):

5 **if** len(matrix[i][j]) == 0:

6 **return** False

7

8 **return** True

9

10 **def** solve(matrix):

11

12 reduce(matrix)

13

14 **if not** solutionViable(matrix):

15 **return** None

16

17 **if** solutionOK(matrix):

18 **return** matrix

19

20 **print**("Searching...")

21

22 **for** i **in** range(9):

23 **for** j **in** range(9):

24 **if** len(matrix[i][j]) > 1:

25 **for** k **in** matrix[i][j]:

26 mcopy = copy.deepcopy(matrix)

27 mcopy[i][j] = set([k])

28

29 result = solve(mcopy)

30

31 **if** result != None:

32 **return** result

33

34 **return** None

In the *solve* function of Sect. 6.6.2, *reduce* is called to try to solve the puzzle with the rules of the last chapter. After calling *reduce* we check to see if the puzzle is still solvable (i.e. no empty sets). If not, the *solve* function returns *None*. The search proceeds by examining each location within the matrix and each possible value that the location could hold. The *for k* loop tries all possible values for a cell with more than one possibility. If the call to *reduce* solves the puzzle, the *solutionOK* function will return *True* and the *solve* function will return the matrix. Otherwise, the *depth first search* proceeds by looking for a cell in the matrix with more than one choice. The function makes a copy of the matrix called *mcopy* and makes a guess as to the value in that location in *mcopy*. It then recursively calls *solve* on *mcopy*.

The *solve* function returns *None* if no solution is found and the solved puzzle if a solution is found. So, when *solve* is called recursively, if *None* is returned, the function continues to search by trying another possible value. Initially calling *solve* can be accomplished as shown in Sect. 6.6.3 assuming that *matrix* is a 9 × 9 matrix of sets representing a Sudoku puzzle.

## Calling Sudoku's Solve Function

1 **print**("Begin Solving")

2

3 matrix = solve(matrix)

4

5 **if** matrix == None:

6 **print**("No Solution Found!!!")

7 **return**

If a non-None matrix is returned, then the puzzle is solved and the solution may be printed. This is one example where no tree is ever constructed, yet the search space is shaped like a tree and depth first search can be used to search the problem space.