Animation: Backtracking

Animation Systems Collection -- Animations Collection

Description

The strategy of backtracking consists of dividing the problem to be solved into a number of subproblems, so that a decision tree is created. For reasons of time and space this tree usually is not actually created, it functions more as an orientation guide.

The branches are then systematically processed until the first solution is found at which point the procedure terminates. Paths with "dead ends" are marked as not possible.

In the worst case the calculation of the entire tree is necessary, which leads to exponential cost.

The animation uses the 4-Queens Problem as an example, in which four Queens have to be placed in such a way on a 4x4-field so they can not strike each other. The 4-Queens Problem is a smaller version of the 8-Queens Problem. It is easy to see that there is no solution for 2 or 3 Queens on a 2x2 or 3x3 field.

Under the field with the Queens the algorithm is described verbally. The separate steps are highlighted using colours.

Screen Shot(s):

Basic Idea

4 Queens Problem - Possible moves for a queen

Dead end reached

Step back ("backtrack") and continue with next possible setting

Classification

• Algorithms
• Algorithmic Strategies

Animation Rating

You can provide a rating for this animation. The rating is performed on a scale of 1 to 10, where 10 is the highest possible grade.

1(very bad) 2 3 4 5 6 7 8 9 10(very good)

File information

Title	Backtracking
Animation URL	http://www.animal.ahrgr.de/Anims/en/backtracking.aml
Animation Applet	Animal Applet
Animation System	Animal
Animation Type	dynamic full VCR
Supported OS(s)	Linux,MacOS,Windows 95,Windows 98,Windows ME,Windows NT,Windows 2000,Unix
Author(s)	Guido Rößling
Date	1999-05-03
File Size size	5245 Byte
Number of Accesses:	17133
Added to DB by	Guido Rößling
Average Rating	4.8544(103 submitted ratings)
Language:	en
Number of Accesses:	17133

BibTeX bibliographic entry for citations:

@Misc{Rößling:1999,
   author = {Guido Rößling},
   title = {Backtracking},
   howpublished = {WWW: \url{http://www.animal.ahrgr.de/Anims/en/backtracking.aml}},
 }