Computational methods: Use of abstraction and backtracking

Overview

Recall questions on abstraction in computational solutions and the danger of abstracting too much, abstraction with decomposition, backtracking in mazes and the four queens problem, its limitations, and problems that suit backtracking.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is abstraction, and what does it do for a computational solution?

   Model answer

   Removing or hiding the detail that does not matter for the problem in hand, so that what remains is simple enough to reason about and to program. A route planner abstracts a whole country down to junctions and the roads joining them with a cost on each — a graph — and discards buildings, scenery, road surface and everything else, because the shortest-route problem needs only the connections and their costs. Abstraction makes a problem small enough to solve at all, makes the model reusable for other problems of the same shape such as a rail network or a computer network, and lets each layer of a large system be built by people who need not understand the layer beneath.

2. 2

   What is the danger of abstracting too much?

   Model answer

   If detail that actually matters is thrown away, the model produces confident answers that are wrong in the real world. A route finder that abstracts roads to distance alone will send a lorry down a lane with a weight limit, ignore one-way streets and roadworks, and take no account of the time of day. A flood model that abstracts away the drains will misjudge which streets fill. Deciding what may be discarded is a judgement about this specific problem: the same real thing needs different abstractions for different purposes, and any model must be validated against reality before its output is trusted.

3. 3

   How do abstraction and decomposition work together on the same problem?

   Model answer

   Decomposition splits a problem into parts; abstraction decides how much detail each part has to carry. In designing a chess program, decomposition gives sub-problems such as represent the board, generate the legal moves, evaluate a position, choose a move, and present the game. Abstraction then says the board can be an eight-by-eight array of piece codes with nothing about the material the pieces are made of, and that evaluating a position can be reduced to a single number. Abstraction is also what lets the parts be used without knowing each other's insides: the move chooser needs only the number the evaluator returns, not the reasoning behind it.

4. 4

   What is backtracking?

   Model answer

   A systematic way of searching for a solution that is built up one choice at a time. You make a choice, test whether the partial solution could still lead to a valid answer, and if it could, move on to the next choice. If it could not, you undo — backtrack — the most recent choice and try the next alternative at that point; if the alternatives there are exhausted too, you back up a further step. It is a depth-first search of the tree of possible choices, with whole branches pruned as soon as they are known to be hopeless. It is usually written recursively, because the call stack naturally remembers the choices that will need undoing.

5. 5

   Show how backtracking solves a maze, and say why it beats simply trying every route.

   Model answer

   Start at the entrance and repeatedly move into an unvisited neighbouring square, marking each square as part of the current path so you cannot go round in circles. If you reach a square with no unvisited way forward — a dead end — step back to the previous square on the path, record the direction just tried as exhausted so it is not repeated, and take the next untried direction from there. If that square has no untried directions either, back up again. Eventually you either reach the exit, and the squares still marked form the route, or you back up all the way to the entrance with nothing left to try, which proves there is no route at all. It beats trying every complete route because a wrong branch is abandoned the moment it dead-ends, so the whole subtree of paths beyond it is never explored.

6. 6

   Explain how backtracking places queens on a chessboard so that none attacks another, using a four-by-four board to show the undoing.

   Model answer

   Exactly one queen goes in each row, so the only choice per row is which column. Place a queen in row 1, then find the first column in row 2 that is not attacked — not the same column and not on a diagonal — and carry on down the rows. If a row has no safe column at all, backtrack: remove the queen from the previous row and move it to its next safe column, then continue. On a four-by-four board: put the queen in row 1 column 1; the first safe column in row 2 is 3; row 3 then has nothing safe, since columns 1 and 3 clash by column and columns 2 and 4 are on diagonals from the queen at row 2 column 3. So back up and move row 2's queen to column 4. Row 3 can now take column 2, but row 4 then has nothing safe, and row 3 has no further options, and nor does row 2 — so back up to row 1 and move that queen to column 2. From there row 2 takes column 4, row 3 takes column 1 and row 4 takes column 3, which is a valid solution: columns 2, 4, 1, 3 for rows 1 to 4. The saving is that a bad first choice is abandoned after examining a handful of squares rather than after testing every way of placing four queens.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.