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

1. 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 passes each junction.
• Public transport planners like Amtrak.


• Dijkstra's algorithm When you know if some stops are directly connected (without a stop in between) you can optimize processing.


• Car navigation software (TomTom) and in Google Maps


• Internet-navigation, the path of an HTTP or SMTP-message over the internet


• Planning of Newspaper rounds in Manhatten, programming contest, organised in 1996 by Telegraaf


• See also: Local search method.



Schedule optimization:
• Creating a country-wide 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 contra-candidates from the same list)
• (Speed)Dating - match a list of candidates to a list of contra-candidates (supposed you have rounds where all candidates switch simultaneously to the next)


2. Mind games (using a minimax algorithm and Alpha-beta pruning)
• Chess. An experienced player could beat the old 'Chess Challenger' quite easily, but have you tried a modern program like 'Deep Blue' or 'Deep Fritz'? Only the strongest players can win some games against payable software.
• With dames the same, only the best players have any chance to beat the computer.
• Connect-4 (4 On a Row), has been solved by the computer! The first player can force a win.
• With Othello (reversi) human players can't compete any more.
• Go (asian board game), these programs got much stronger recently.
  Breaking news: The computer has won against the strongest player from Europe.
  In march 2016 a match has been organized between the current world Go-champion Lee Sedol and the computer program AlphaGo. AlphaGo won with 4 by 1. This caused quite a shock in the Go world! This strong program is not for sale yet.

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!


3. Puzzles (and most programming contests)
• the 8 queens problem (a case-study)
• Mathematical jigsaw puzzles I have some solvers in Windows (Free download)
• Moving block puzzles (Rush Hour, the piano-mover, bishop-problem, 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 TV-programme '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 make the computer understands the clue-sentences?
  This is realizable 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.
• The computer games The 7th Guest and The 11th hour contain a number of nice puzzles that can be solved (or played against) the computer.

• Recursion - You write a subroutine that calls itself, in a way it repeats the exercise with a subset of the exercise.
  Othen, your program may look amazingly simple, and still it does the full job! see Towers of Hanoi
• One big 'while'-loop, is more flexible to control the flow and data..
• Using a recursive language like Prolog, the base program has already been done for you. These languages can be a bit lavish with memory or CPU, so for the larger tasks this might not be the best way.