# What is a maze problem

### 3.1.4 Examples of backtracking procedures

Some examples of backtracking that are well suited for teaching due to their clarity are mentioned here. By
the literature reference is referred to a more precise formulation.

The Königsberg bridge problem
In the city center of Königsberg, the Old and New Pregel merge to form the Pregel River. In the 18th century, the
River runs seven bridges. We are looking for a path that leads over each bridge exactly once. [Duden Computer Science,
Engesser / Claus / Schwill, Dudenverlag, Mannheim, 1993, p. 347]

The maze problem
You are in a maze and try to find a way out. [Duden Informatik, Engesser / Claus / Schwill,
Dudenverlag, Mannheim, 1993, p. 51]

N queens are to be placed on an n x n chessboard in such a way that no queen threatens another. [Algorithms and
Data structures, N. Wirth, Teubner Verlag, Stuttgart, 1983, p. 168 ff.]

The problem of stable marriage
Couples are formed from a crowd of men and a crowd of women. Every woman and every man has one
Wish list of partners in the order of their preference. When the married couples are chosen to make one
There are men and women who are not married to each other, but who are mutually prior to their actual spouses
would give preference, the choice is unstable. If there is no such pair, the choice is stable. [Algorithms and
Data structures, N. Wirth, Teubner Verlag, Stuttgart, 1983, p. 174 ff.]

The backpack problem
A backpack with a maximum carrying capacity should hold objects of different mass and different values
be packed. The carrying capacity of the rucksack must not be exceeded; on the other hand, the value of the items should be
get as big as possible. [Duden Informatik, Engesser / Claus / Schwill, Dudenverlag, Mannheim, 1993 p. 606 f.]

The jumper problem
Starting from a starting square, a knight looks on a chess board according to the rules of chess for a path that precisely matches him
once across each field. [Algorithms and data structures, N. Wirth, Teubner Verlag, Stuttgart, 1983, p. 163 ff.]

Neighborhood problems
Pennants of different colors and different numbers should be hung up so that there are no two adjacent pennants
have the same color [15. Federal IT competition, task 1]

Path problems
A traveling salesman is supposed to travel to certain places. [Basic and advanced course in computer science, Rollke, Sennholz, Cornelsen,
Berlin, 1994, p. 109 ff.]

### 3.1.7 Literature

[Algorithms in C, R. Sedgewick, Addison-Wesley, 1993]
[Algorithms and data structures, Ottmann / Widmayer, Spektrum Verlag, 1996]
[Algorithms and data structures, N. Wirth, Teubner Verlag, Stuttgart, 1983]
[Duden Informatik, Engesser / Claus / Schwill, Dudenverlag, Mannheim, 1993]
[Uniform examination requirements in the computer science Abitur examination, Luchterhand, 1991]
[Basic and advanced course in computer science, Rollke, Sennholz, Cornelsen, Berlin, 1994]
[Principles of the Agorithm Draft, T. Ottmann, Spektrum Verlag, 1998]