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 subbranches).
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 rejected in an early stage, when it coms clear
that it won't be successful. This way you can optimize the process strongly.
Case study: the 8 queens problem
When can you use backtracking?
The applications can be catechorized:
 Common applications
 searching through a directory with subdirectories (recursive)
 Some sorting algorithms use recursion
 Travelling salesman. Suppose you have a distance table of a set of destinations.
Calculate the shortest or fastest route that visit all destinations.
 Schedule optimization:
 Creating a countrywide schedule for trains, train staffing, railroad sections and platforms.
 Optimize a school schedule for lessons, students, teachers and lesson rooms.
 Optimizing Demand and Supply e.g. with
Linear programming
in Operational Analysis.
 Incomplete Block Design e.g. for Marketing Research, product testing:
Suppose you need to have 8 variants been tested, but for practical reasons you can only test 4 variants
per respondent.
With 4 out of 8 you can create 70 combinations (8 over 4 = (8*7*6*5)/(4*3*2*1) = 70) so you would need 70 test groups.
luckily in this case it's possible to make a set of 14 groups in a
Balanced Incomplete Block Design.
 Tournament/competition scheme (canditates and contracandidates from the same list)
 Dating  match a list of candidates to a list of contracandidates (in theory)
 Mind games
(using a minimax algorithm
and Alphabeta pruning)
Computers are better 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 Alphabeta algorithm,
in chess terms: find a surprising
Queen sacrifice!
 Puzzles (and most programming contests)
 the 8 queens problem (a casestudy)
 Mathematical jigsaw puzzles I have some solvers in Windows (Free download)
 Moving block puzzles (Rush Hour, the pianomover, bishopproblem, rubiks cube)
 Solving
the Peg Solitaire puzzle
and: in as few moves as possible.
 Creating a maze or labyrinth
as well as solving it!
Algorithms
 Solving Numbers
from TVprogramme 'Letters and Numbers'
 Logiquiz puzzles (dutch)
With a number of clues you are requested to find the correct matrix of attributes.
Extra challenge for a generic solution: hoe can you transelate a cluesentence to somthing the computer understands?
This is only possible when the clues follows a restricted set of transelatable structures.
 Sudoku (for creating as well as solving), introduction...
 Create a magic square with a set of domino stones
 See also the book 'Spelen met Puzzels' (dutch: Playing with Puzzles) 1978 by Pieter van Delft and Jack Botermans,
for a almost unlimited resource of mind teasers.
 de computer games The 7th Guest
and The 11th hour
contain a number of nice puzzles that can be solved (or played against) the computer.
There are different styles (each with its own advantages):
 Recursion  You write a subroutine that calls itself,
in a way it repeats the exercise with a subset of the exercise.
Your program may look amazingly simple, and still it works!
Old or primitive programming languages didn't support this very well,
modern languages like C, Delphi and Visual Basic perform recursion very well.
 One big 'while'loop, this can be worked out in nearly any language.
 Using a recursive language like Prolog, the base program has
already been done for you.
These languages are often a bit lavish with memory,
so for the larger tasks this might not work very well.
Links:

The N queens problem, magic squares and more
 Genetic algorithm