A Python implementation of the Snakes and Ladders for solving the Hamiltonian cycle problem using a graphical interface

Abstract

[EN] Given a graph, the Hamiltonian cycle problem (HCP) consists of finding a cycle in a given graph that passes through every single vertex exactly once, or determining that this cannot be achieved. This problem has several applications in Industry and Transport such as scheduling problems, routing and plannification problems. The HCP is very well-known NP-complete problem for which several heuristic approaches have been proposed in the literature. One of the most efficient methods is the "Snakes and Ladders" Heuristic (SLH) which is of polynomial complexity and deterministic approach. The goal of the project is to implement the SLH together with a simple web-based interface. A graph is entered as a file, the interface visualizes the graph and represents the partial solutions found by SLH as it searches for the HCP solution. The algorithm will be validated using challenging graphs.