File KnightTour.h

↰ Parent directory (ADS/backtrack)

The tour of the knight (exercise 16.6): a path of the knight that visits every square of an n x n board once.

Definition (ADS/backtrack/KnightTour.h)

Detailed Description

cavallo() of the book tries the 8 moves in a fixed order and backtracks from the dead ends, which on an 8 x 8 board may take very long; the rule of Warnsdorff tries first the moves to the squares with the fewest onward moves, and with it the backtrack seldom happens, a tour of a board of hundreds of squares in linear time. Both return the board with the step of each square, from 1, or nothing if there is no tour from the given square.

The contracts [see File Contract.h]: the start is on the board, and the tour found moves as a knight from it (checked at level 3). The operations are defined in KnightTour.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, exercise 16.6, https://algoritmicamente.it/materiali/libro/capitoli/cap16.pdf

    1. von Warnsdorf, Des Roesselsprunges einfachste und allgemeinste Loesung, Schmalkalden, 1823

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions