DCP Project

An example of a knights tour board where the knight touches each square once and returns to its starting position (image: Wikipedia)

Solving the Knight’s Tour Problem with Distributed Computing

This project is meant to solve the famous Knight's Tour problem using distributed computing, specifically the closed Knight's tour variant. In simpler terms, the program attempts to find a path that allows a knight to visit every single square on a chessboard (although a board of any size can also be solved, while different shapes can also be done with some modification) and ends where it starts, creating a loop. This essentially means that the knight can start from wherever on the board and can still finish the tour. The project makes use of Warnsdorff's heuristics with randomized choices in combination with the divide and conquer strategy, using custom board partitioning and merging algorithms.

Watch the presentation here.

Khoa Nguyen
Developer @ DCP
Third year Computing student at Queen’s University, specializing in software design
Mehedi Arefin
Developer @ DCP
Computer Science MSc (‘22) from Lakehead University