Two-Piece Hamiltonian Chessboard Tour
A Java Swing backtracking solver for a 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.
Two-Piece Hamiltonian Chessboard Tour
Practice 2 for the Advanced Algorithms course (21747) at the Universitat de les Illes Balears. A Java Swing application, on a Model–View–Controller architecture, that solves a backtracking variant of the classic knight’s-tour problem: two pieces share a single Hamiltonian tour of a chessboard, moving in alternating turns, with the extra rule that at no instant may either piece be in a position to capture the other.
The problem
Given a board and two pieces, the goal is a recursive tour that visits every square exactly once, where the two pieces take turns advancing along the same path. 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.
About
- 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.
Executing the project
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.