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.

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 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.

How does backtracking work?

Demo: click on run! to see the puzzle at work on your screen

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:

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

It should be clear now which method works best.

Algorithm of the 'N' Queens Problem (with the 'while' procedure)