Backtracking

Backtracking is a fascinating programming technique wich can be used for optimisations, solving puzzles (jigsaw and other) and creating computer opponents in thinking 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 he reaches the top of a branch, he goes back along the same track as he came, and tries another branch. Sometimes the complete tree is searched, but when the tree is too large, the tree is searched until a certain heigth.

There are different styles:
a> Recursion - Basicly you write one subroutine that calls itself. Your program may look amazingly simple, and still it works! Some more primitive programming languages don't support it very well, modern languages like C, Delphi and Visual Basic work very well with recursion.
b> One big 'while'-loop, this can be worked out in nearly any language.
c> Using a recursive language like Prolog, the base program has already been done for you. These languages are often a bit lavish with processor stack and memory, so when you need to go very deep into the 'tree', this might not be the best approach.

The applications can be catechorized in 3 groups:

1) Optimisation-problems in businesses
- Travelling salesman / bus-line algorithm
- Creating best schedules:
--- Dating (match a list of candidates with a list of contra-candidates)
--- Tournament/competition scheme (canditates and contra-candidates from the same list)
--- Creating an incomplete block design e.g. for marketing research (product testing)
--- matching Supply with Demand
- searching through a directory with subdirectories 2)Backtracking has been used succesfully in thinking games
- Chess. An experienced player can easily beat the old 'Chess Challenger', but have you tried a modern program like 'Deep Blue' or 'Deep Fritz'? Humans are starting to lose this game from the computer.
- dames
- 4 on a row, there exist some unbeatable programs!
- Othello / reversi
- Go (asian board game), these programs become slowly stronger, but are not yet very dangerous for stronger human players. With Go it is quite difficult to judge a position.

Humans are feeling (worried about his own place) that the computer is in progress to become a 'thinking machine'. You make more chance chance against the computer opponent either if you make a better a better selection of moves to evaluate, and so be possibly able to go deeper into the moves-tree, or you have better judgement about the board possitions you meet. When the computer is able to search the complete tree he can play perfectly unbeatable!

Links:
- the microscope game from The 7'st guest
3) Puzzles (and programming contests)
- Mathematical jigsaw puzzles
- Moving puzzles (the piano-mover, bishop-problem, rubiks cube)
- Solving the Solitaire puzzle (and: in as few moves as possible)
- Creating a maze or labyrinth as well as solving it!
- logikwis (I don't know the English term)
- sudoku
- A magic square with a set of domino stones
- See also the book 'Spelen met Puzzels' dutch 1978 by Pieter van Delft and Jack Botermans, for a nearly unlimited source of mind teasers.
- The games 'The 7th Guest' and the '11th hour' contain a number of puzzles that can be solved (or competed) by a PC

Links:
- The N queens problem, magic squares and more