Backtracking is well illustrated met the 8-queens puzzle. The rules of this puzzle are:

• Take a chess board (8 x 8 fields), with 8 queens of the chess game, you can also use pawns or anything that fits on a field.
• Put each of the 8 queens on a field on the board in such a way that no one is seeing any other queen, according to the chess rules. That means the are never in a line:
• not in the same column
• not on the same row
• not on the same diagonal row
• The size (8) Doesn't matter for the rules. You could start more simple e.g. with 5, on a board of 5 x 5 fields with 5 queens.
• So try to find a solution (even beter: find ALL solutions) to place all queens on the board.
Solution with 5 queens

Before I explain how backtracking works, let's have a look at the alternatives.

## Brute force:

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.

## Optimised Brute force:

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 88 = 16,777,216 positions to evaluate. This approach is must faster, ca. 250x as fast! But still some amount of work for the computer.

## How does backtracking work?

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.

At the first row? No, there already is another queen on it.
At the second row? No, there is a queen on the same diagonal row.

At the third row? Yes, that's fine!

We can move up another column for the next queen.

But whatever we try ... there is no field at all where we can place a queen.

We go back to column 2 and move up the queen to row 4.

That's okay.

Again move up to column 3. The first row is wrong

But the second row works well.

For the first time we reach the fourth and last column!

But unfortunately there is no proper field for the last queen.

that is a pity! We have to go back to column 3...

But unfortunately we haven't any proper field left for this queen.

Back to column 2...

But this queen was already on the last field...

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.

Who knows this works better?

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.

That's nice!

And finally to column 4 ... en there's the first solution!

In just 26 moves moves.

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:

• Brute force: (16 over 4) = 16 x 15 x 14 x 13 = 43.680 positions, x 4 queens = 174.720 moves.
• Optimized brute force: 44 = 256 positions, x 4 queens = 1024 moves.
• Backtracking: 40 moves.

It should be clear now which method works best.