9.1. Constraint Solving via Backtracking
File:
Backtracking.ml
Constraint solving problems are extremely common in Computer
Science. In the most abstract form a constraint problem deals with a
finite set of variables x1, x2, … xn that can be
assigned multiple values, in the most common cases those values being
0 and 1. In addition to the set of variables, each problem
comes with a number of constraints defined as predicates (boolean
functions) that render certain assignment schemes to the variables as
undesirable. Therefore, you can think of constraint systems as of
systems of equations and inequalities on x1, x2, … xn,
and their solutions to be the values of x1, x2, … xn
that satisfy all the constraints.
Another example of a constraint problem is allocating N students
into groups, such that each group would have between m and k
members. The problem could be solved by a simple division, but in the
presence of constraints (a student A does not want to be in the
same group with a student B), the finding solution becomes less
trivial. While humans are good in solving constraint-satisfaction
problems for small number of variables (e.g., 20 or less), it becomes
quite tedious as the number fo involved variables grows, and should be
implemented as a computer program.
9.1.1. Constraint Solving by Backtracking
In practice, most of constraint satisfaction problems (CSPs) do not have an efficient solution, and fall into the category of intractable, having complexity \(O(2^n)\) or \(O(n!)\) in the number of involved variables. Nevertheless, they still arise very often in practice and hence we need to know how to tackle them algorithmically.
The stated complexities \(O(2^n)\) and \(O(n!)\) hint that in order to solve a CSP we often need to enumerate all subsets or even all permutations of the set of variables. This is due to the fact that for a set of \(n\) distinct elements, the number its subsets would be \(2^n\) and the number of permutations would be \(n!\).
When enumerating subsets or permutations, we should take constraints
into the account. Instead of trying all permutations/subsets randomly,
we can do slightly better by constructing the solution incrementally,
while checking the constraints at each intermediate step. However, it
might also be the case that, while taking a certain route when
assigning values to x1, x2, … xn, we have went in a
“wrong way”. In this case, the algorithm for gradually constructing
the solution, the algorithm needs to back-track to the partial
solution, which did not (yet) violate the constraints, and try a
different path. Eventually, either the full solution satisfying all
constraints is discovered, or no solution is found (in which case CSP
is unsolvable). As a graphical analogy, you can think of CSPs as
walking by the branches of a “decision tree” towards possible
solutions, back-tracking when a certain branch does not work. This is
somewhat reminiscent to the tree of sorting possibilities discussed in
Section Best-Worst Case for Comparison-Based Sorting.
9.1.2. Computing Solutions with Backtracking
In the light of the tree-analogy described above, let us remark that each algorithm implementing a CSP solution by search via back-tracking combines two computational patterns:
Iteration (e.g., via
for-loop) — for enumerating possible alternatives (branches) to consider at a given stage.Recursion — for going deeper into a certain branch, in a hope that it will bring us closer to a solution.
9.1.3. Examples of CSP solved by Backtracking
The tree-based analogy and back-tracking is widely applicable for solving NP-complete problems, such as
We will consider some of these problems later in this class, but in this section focus on a simpler (and less practically useful) problem solved by backtracking, namely N-Queens problem.
9.1.4. N-Queens problem
Assume you are given an n by n chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. We are going to discover this solution iteratively, via back-tracking, by considering it a CSP.
Question: does the solution exist fo any n?
The board is encoded as 2-dimensional array board of integers (0
or 1). We are going to put queens, iteratively, in each column,
starting from the left, and moving right. To check the safety of a
partial solution, before placing a new queen in a row row and a
column col, we define the constraints, that check that no other
queen on the left part of the board threatens it:
let is_safe board row col =
let n = Array.length board in
(* Check this row on the left *)
let rec check_row_left i =
if i < 0 then true
else if board.(row).(i) = 1 then false
else check_row_left (i - 1)
in
let rec check_left_up_diag i j =
if i < 0 || j < 0 then true
else if board.(i).(j) = 1 then false
else check_left_up_diag (i - 1) (j - 1)
in
let rec check_left_down_diag i j =
if i >= n || j < 0 then true
else if board.(i).(j) = 1 then false
else check_left_down_diag (i + 1) (j - 1)
in
check_row_left col &&
check_left_up_diag row col &&
check_left_down_diag row col
The following procedure demonstrates back-tracking by combining the iteration and recursion. It rakes a board and its size n and solves the problem (or discovers that it is unsolvable) starting from the column col, assuming the columns on the left are already taken care of:
let rec solver board n col =
let rec loop i =
if i = n then false
else if is_safe board i col
then begin
board.(i).(col) <- 1;
if solver board n (col + 1)
then true
(* Back-tracking *)
else begin
board.(i).(col) <- 0;
loop (i + 1)
end
end
else loop (i + 1)
in
if col >= n
then true
else loop 0
The main work is done by the recursive function loop i,
implementing the iteration through rows for a fixed column
col. Whenever loop reaches the bottom row (i = n) it stops
and returns true, indicating that the solution is found.
Alternatively, it tries to install a queen to a position
board.(i).(col) and solve the remaining problem by moving to the
next column (solver board n (col + 1)). In case if this has
failed, it back-tracks (by un-installing the queen) and tries a
different row.
The top-level program simply calls solver from the leftmost column:
let solve_n_queens board =
let n = Array.length board in
let _ = solver board n 0 in
board
Question: what is the complexity of solve_n_queens in terms of the size of the board?
We can check the result via the following functions:
let mk_board n =
let board = Array.make n (Array.make n 0) in
for i = 0 to n - 1 do
board.(i) <- Array.make n 0
done;
board
let print_board board =
let n = Array.length board in
for i = 0 to n - 1 do
for j = 0 to n - 1 do
Printf.printf "%d " board.(i).(j);
done;
print_endline ""
done
For instance, for n = 8 the outcome is as follows:
utop # let b = mk_board 8;;
val b : int array array =
[|[|0; 0; 0; 0; 0; 0; 0; 0|]; [|0; 0; 0; 0; 0; 0; 0; 0|];
[|0; 0; 0; 0; 0; 0; 0; 0|]; [|0; 0; 0; 0; 0; 0; 0; 0|];
[|0; 0; 0; 0; 0; 0; 0; 0|]; [|0; 0; 0; 0; 0; 0; 0; 0|];
[|0; 0; 0; 0; 0; 0; 0; 0|]; [|0; 0; 0; 0; 0; 0; 0; 0|]|]
utop # solve_n_queens b;;
- : bool * int array array = ...
utop # print_board b;;
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
- : unit = ()