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.