This labsheet is in two parts: a number of review exercises that reinforce concepts from the lectures; and an important problem-solving technique, motivated by its use in solving a larger-sized problem representative of the types of problems that can be solved with computers.
Consider the "verbal arithmetic" puzzle SEND + MORE = MONEY. The requirement is to assign one of the digits 0, 1, ..., 9 consistently to each of the eight letters in the puzzle so that the arithmetic works correctly. There are various constructive ways to solve this type of puzzle which depend on logic and maths, but what is a good generic approach?
One way is to use enumeration, as in Lab 5. We might assign a digit to D, then assign a different digit to E, then assign different ones to each of the other letters, and when the assignment is complete, check whether the arithmetic works. But of course the problem is that with ten digits and eight letters, there are 1,814,400 distinct assignments, so this would be quite slow, even for such a small puzzle.
A better way is to use backtracking, which is similar to enumeration except that every time we assign a digit to a letter, we check immediately whether a solution is still possible. So if we assign 4 to D, then 7 to E, then 2 to Y, we can say immediately that we have gone wrong, because the sum in the rightmost column doesn't work (4 + 7 = 11, so Y can't be 2). The early termination of this sequence of assignments saves a lot of work and makes the process much faster.
As a second example, consider doing a Sudoku puzzle. If we reach a point where we can't identify any square with only one possible number, then we might guess a number for one of the squares, then continue the puzzle under the assumption that the guess was correct. Then if at some later time we hit an impossible situation, we go back - we backtrack - to that guess and try a different number. This also is backtracking.
The basic structure of backtracking is as follows:
if not reject(soln):
for each way of extending soln:
bt(extension of soln)
and we invoke this function with bt(initial soln).
To apply backtracking to a real problem, we need to provide four facilities:
PROBLEM SOLVING QUESTION 6.1) The classic problem solved using backtracking is the 8-queens problem: place eight queens on a standard chess board such that no queen attacks any other queen. (Recall that a queen can move any number of squares horizontally, vertically, or diagonally, so effectively we are asking that no queens share a row, column, or diagonal.) The more-general version is the n-queens problem, which extends the idea to chess boards of size n x n.
Define the four facilities outlined above and put them into the backtracking framework to construct a Python funcion nqueens(n) that generates all solutions to the n-queens problem, and displays them using turtle graphics.