Backtracking is well illustrated met the 8-queens puzzle. The rules of this puzzle are:
Before I explain how backtracking works, let's have a look at the alternatives.
We generate each possible positions of 8 queens on a board, and for each position we evaluate whether it is a solution or not. Of course there will be a number of silly positions with all queens clustered together like here below.
The computer might get a tough piece of work...
There exists (64 over 8) postions = 64!/((64-8)!*8!) = 4,426,165,368 positions.
For each position a number of queen pairs (max. 8*7/2= 28) must be examined if they are in no way on the same line.
This will definitely cost an amount computer time. Imagine what happens if you would like to try a larger puzzle too.
We can improve the previous method, since we know that each column may hold only one queen. We now generate all posible positions where each column holds only one queen, There will be silly positions again, but not as silly as in the previous method, e.g.
Now there are 8^{8} = 16,777,216 positions to evaluate. This approach is must faster, ca. 250x as fast! But still some amount of work for the computer.
Demo: click on run! to see the puzzle at work on your screen
Size:
Basic principle is that we already evaluate when we put a queen on the board,
if the queen is on the line of one other we first find a proper field, before take the next queen.
Let's do it step by step with our bare hand. And we keep it fairly simple by choosing the puzzle of size = 4.
It starts with an empty board. Then go to column one and place a queen on the first row of it.
Then we go to the next column to find a place for queen #2.
We can move up another column for the next queen.
We go back to column 2 and move up the queen to row 4.
Again move up to column 3. The first row is wrong
For the first time we reach the fourth and last column!
that is a pity! We have to go back to column 3...
Back to column 2...
So we are back to column 1 and try this queen on the second row. You should now have a good idea why this method is call back-tracking.
Next is column 2, the queen can be placed on the last row only.
Now there is column 3, the queen fits directly on the first row.
And finally to column 4 ... en there's the first solution!
We're not finished yet, we'd like to know ALL solutions.
But for the demo we'll keep it like this.
There exists a second solution, which is in fact a mirror of the first.
Finally the algorithm will have tried all fields of column one,
it will consequently go back to column 0 (which doesn't exist) and it should stop.
Summary for the 4x 4 puzzle:
It should be clear now which method works best.