In-depth Backtracking with LeetCode Problems — Part 3
Solving Constraint Satisfaction Problem (CSP) with Prunning
Before reading this post, read part one and two first:
Backtracking with LeetCode Problems — Part 1: Introduction and Permutation
Backtracking with LeetCode Problems — Part 2: Combination and All Paths
We can cut unnecessary branches in the search tree with two methods:
Search Prunning
In previous sections, we have learned how backtracking can be applied to enumerating based combinatorial tasks such combination, permutation, and all paths in graph. In this section, we state how backtracking can be optimized with search prunning in CSP. Suppose we are at level 2 with state s=(s_0, s_1, and if we know that this state will never lead to valid solution, we do not need to traverse through this branch but backtrack to previous state at level one. This will end up prunning half of all nodes in the search tree. We demonstrate the technique with Sudoku problem.
Symmetry
Exploiting symmetry is another avenue for reducing combinatorial search, prunning away partial solutions identical to those previously considered requires recognizing underlying symmetries in the search space. This technique will be demonstrated with classical Eight Queen problem.
Sudoku
Problem Definition
Given a partially filled grid of size n*n, completely fill the grid with number between 1 and n. The constraint is defined as:
- Each row has all numbers form 1 to ‘n’
- Each column has all numbers form 1 to ‘n’
- Each sub-grid ( √(n)×√(n)) has all numbers form 1 to n
Only all constraint are satisfied can we have a valid candidate. How many possible candidates here? Suppose we have an empty table, the brute force is to try 1 to n at each grid, we have possible solution space of nⁿ². How many of them are valid solutions? We can get closer by permutating numbers from 1 to 9 at each row, with 9!⁹ possible search space. This is already a lot better than the first. How to know the exact possible solutions? This site demonstrates that the actual N=6670903752021072936960 which is approximately 6.671×1⁰²¹ possible solutions. This shows that sudo problem is actually NP-hard problem.
Solving Sudoku with Backtracking
ow, let us see how we can use backtrack and search prunning to implement a sudoku solver. Our solution vector s will a length for all empty spots in the given grid. And each item in the vector represents an event for corresponding spot, which might have any number of candidates in the range of 9, just like in the case of permutation, each level’s candidates is constrained by the previous state. In the case of sudoku, we set aside three data structures row_state, col_state, and block_state to validate a candidate. Like any other backtracking algorithm, there are mainly two steps:
- Initialization: we initialize the three states and prepare data structure to track empty spots.
- Backtrack: we use DFS to fill in empty spots in a type of ordering.
Step 1: Initialization
We use (i,j) to denote the position of a grid. It correspond position i in row_state[i], and j in col_state[j], and block_state[i//3)][ j//3] for corresponding sub-grid. The code is shown in function init at line 7–22.
Step 2: Backtracking and Search Pruning
Now, we iterate the empty spots and each time we choose to fill in the spot that with the least number of candidates. To compute the candidates, we can use a set union and set difference A-(row_state[i]|col_state[j]|block_state[i//3][j//3]). We set the time cost for this is O(9), and each time the time cost to pick the best one is O(9n), where n is the number of total empty spots. The total time complexity is O(n²). Compared with the time complexity of cⁿ, where c is the average number of candidate for each spot, the time spent here is trivial.
In this problem, backtrack happens if the current path can not lead to valid solution. First, for an empty spot following on the path that has no candidate to choose from (line 45–46), then it is an invalid path, and requires backtrack to line 56. Second, for an empty spot, if none of its candidates can lead to valid solution, as shown in code line 51–56, it backtrack to previous empty spot.
Where is the Prunning?
If there is only one path that can lead to the final valid answer, this means for other paths, the earlier we find out that it is invalid and backtrack the better. What techniques we have been used here? We could have visit the empty spots in arbitrary ordering instead of each time in our code to choose the spot that has least candidate.
- Look Ahead: The backtrack search works correctly if we do not update the candidates since initialization, and just simply try each candidate and visit the empty spot arbitrarily as we have down in the naive approach shown in the code. However, a smarter choice is to update candidates for all remaining empty spots for each state change ( the remaining empty spots locate at the same row, col, or grid as of the current attempting spot), we are able to make decision global-wisely. If there is a remaining empty spot that end up with no candidate at all. We can detect that the current state is not valid.
- Most constrained spot selection: In our solution, we obtain this by comparing the number of possible candidates for all the left empty spots and pick the one has the least possible candidates. Probabilitically speaking, if there is one spot in the remaining opening spots that has no candidate at all, then we prune this branch instead of wasting our time and effort to first try others spots and then found out that it is an dead end.
Time Complexity
Assume we have n empty spots, and the number of possible values for each spot are spot= [a₀,a₁, …,an₋₁]. To fill each spot, we need to search the possibility tree. The search tree will have a height of n, at the first level, the width of the tree will be a₀, second level a₁, and as such each level will have a total nodes of ∏ᵢ₌₀⁽ⁿ⁻¹⁾aᵢ= aᵢ!. This will result in worst time complexity O( ∑ᵢ₌₀⁽ⁿ⁻¹⁾aᵢ!).
Note: working on the eight queen part
Resources
To try out the code:
To more content
