Searching
Searching problems are a category of problem solving that can be solved by using generative recursion. This is because we will have to generate the space of all possible paths from a given state and then traverse the space until a solution is found.
The structure of a search function is such that there will be many helper functions defined around it.
Brute Force Search
For some problems, rather than come up with human strategies for solving it, we can come up with a general space of all possible solutions and then pick the best one.
For example, given Sudoku, we can generate all possible boards given a starting state, and then use backtracking search to choose the solution we want.
Sudoku Solver
Domain Analysis
Sudoku is played on a 9x9 board. As a result, there are 81 squares to be filled. Additionally, there are 9 columns, 9 rows, and 9 boxes - each of which is a set of numbers 1 - 9.
This rows, columns, and boxes are all referred to as units. There are 27 units (9 rows + 9 cols + 9 boxes).
The goal of the game is to fill every square with Natural[1,9] without a duplicate number in any unit.
Search Intuition
The basic idea of this problem is that we are going to take a Sudoku board and generate every possibility that stems from that start, looking for a solution.
Given a specific board:
- Fill in the first available space with each possible value a) This generates 9 new possible boards
- Immediately remove invalid boards
- Repeat
In other words, the logic of the solver is to generate an arbitrary arity tree and immediately perform a backtracking search over it. Through the search, we will come, along each branch, to a board with no valid next boards and produce false, or to a board that is full - and therefore the solution, since we have been pruning invalid boards along the way.
Thus, there are 3 aspects to the core structure of this function:
- Generate the tree
- Backtrack over it and prune
- Produce solution