Hamilton

Description

The P versus NP problem is a major unsolved problem in computer science. It discusses whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer. It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a US$1,000,000 prize for the first correct solution. The Hamiltonian cycle problem is a well known NP-complete problem from the Graph Theory field. Solving such problem e.g finding a polynomial algorithm that solves it at any given input, would make humanity closer than ever to solve the P versus NP problem.

In this game you are being given a Graph, that is a set of nodes and edges, which sometimes contains an Hamiltonian cycle (learn more here https://en.wikipedia.org/wiki/Hamiltonian_path_problem) and sometimes does not, and you need to solve it, either by exposing an Hamiltonian cycle or by deciding that it doesnt exists for that graph.

a big tip for deciding weither a graph is hamiltonian (contains an Hamilton cycle) can be found here https://en.wikipedia.org/wiki/Graph_toughness.

Come on and solve a 1 million $ problem, and learn Graph Theory while at it!