Overview

A Java Swing application that solves a backtracking variant of the rook’s tour: two pieces share one Hamiltonian tour of the board, moving in alternating turns, with neither ever able to capture the other.

The tour has to visit every square exactly once, and the two pieces advance along it in turn. The extra rule is what makes the classic problem hard again: at no point may either piece stand where it threatens the other, so a move that is legal on the board can still be illegal in the tour.

The search is plain backtracking: try every legal destination, keep the move only if the position it leaves is safe, recurse, and undo it when the branch dies. The interesting part is how quickly the board size makes that expensive, which the application reports as it goes.

Project 2 of 7 for the Advanced Algorithms course at the Universitat de les Illes Balears, the one on backtracking.

javabacktrackingsearch