Two-Piece Hamiltonian Chessboard Tour
A Java Swing app that solves a backtracking variant of the knight's tour: two pieces share a single Hamiltonian tour of a chessboard, moving in alternating turns, with the rule that neither may ever be in a position to capture the other.
The problem
Project 2 of 7 for the Advanced Algorithms course at the Universitat de les Illes Balears — the one on backtracking, worked through a variant of the classic knight’s-tour problem.
Given a board and two pieces, the goal is a tour that visits every square exactly once, where the two pieces take turns advancing along the same path — with the extra rule that at no instant may either piece be in a position to capture the other. The search is a backtracking exploration: at each step the piece to move tries every legal destination, the move is kept only if it does not leave the two pieces mutually threatening, and the algorithm recurses; when no move works it undoes the last choice and tries the next. Everything parameterizable — board size, the two piece types and the starting configuration — is exposed in the GUI, and the board panel animates the tour as it is found.
Beyond the standard chess pieces the app includes a few invented ones with their own movement and capture rules, so the same solver works over a mix of classic and custom pieces.
How it works
- Backtracking solver — a recursive depth-first search with pruning: a partial tour is abandoned as soon as a piece would be capturable or a square becomes unreachable, and the solver records nodes explored, backtracks and time.
- Pieces as strategies — each piece implements a common
Pieceinterface (Knight,Bishop,Rook,Queen, plus the customAlienandPrism), encapsulating both how it moves and how it threatens, so the solver stays piece-agnostic. - Model — value objects hold the current board occupancy, visited squares, a single tour step and the user-chosen parameters.
- MVC +
Notify— the controller drives the search on a background thread and streams progress to the view through the message contract; the view only renders board snapshots and forwards user actions.
Running it
Requires a JDK 17 or newer — plain Java with Swing, no external dependencies or build tool. Open the P2/ folder in IntelliJ IDEA and run practice2.Main. Pick the board size and the two pieces in the control panel and launch the search to watch the shared tour being built square by square.