Backtracking is an implementation of Artificial Intelligence.
Backtracking is a fascinating way of software engineering which can be used for optimisations, solving puzzles (jigsaw and other) and creating computer opponents in mind games like chess.

There are written many books about this subject, but in short it looks like this:

The computer walks through 'a tree of possibilities' (with branches and sub-branches). Such a branch may mean: fitting one piece of a puzzle, or trying one move in a chess game. When the program has worked out the top of a branch, it follows its track back along the same branch he came, and tries another branch. Another aspect is that a branch can be cancelled at an early stage, if it comes clear that it won't give successful result. This way you might optimize the process strongly.

Case study: the 8 queens problem

When can you use backtracking?

The applications can be catechorized:
  1. Common applications

  2. Travelling salesman. Suppose you have a distance table of a set of destinations. Calculate the shortest or fastest route that passes each junction.
  3. travel solution
  4. Schedule optimization:

  5. Mind games (using a minimax algorithm and Alpha-beta pruning)

  6. Computers are stronger than humans in most mind games.
    You'll only have chance chance against the computer when you find variants that are cut off by the Alpha-beta algorithm,
    in chess terms: find a surprising Queen sacrifice!

  7. Puzzles (and most programming contests)
There are different approaches (each with its own advantages):

- The N queens problem, magic squares and more
- Genetic algorithm