Problem 7: Hamiltonian Path on a Grid

Loyola College > Department of Computer Science > Dr. James Glenn > HS Programming Contest > Problems > Problem 7: Hamiltonian Path on a Grid

Introduction

A graph (in the discrete math sense) is a collection of vertices with edges between them. The Hamiltonian Path problem is that of, given a graph, determining if there is a path through the graph that visits each vertex exactly once. The general Hamiltonian Path problem is thought to be very hard to solve efficiently.


A graph and a Hamiltonial Path through it (the highlighted edges)

Problem

The provided Grid class implements a special form of a graph on a 2-D rectangular grid. Each space in the grid represents the possible location of a vertex in the graph. The 2-D array of booleans (C++: bools) field called verts contains true if the corresponding vertex is present in the graph and false if it is not. Any two vertices that are adjacent vertically or horizontally are connected by an edge; no other edges are present. For example, the array shown on the left (black stands for true and white stands for false) represents the graph on the right.


A grid and the graph it represents

Add a method called hasHP to the Grid class that determines if the grid-graph the method is invoked on has a Hamiltonian Path. The path may begin or end at any vertex that is present. The method should return true if the grid-graph has a Hamiltonian Path and false otherwise. For example, for the grid below on the right the method should return true (one possible Hamiltonian Path is shown for illustration) and for the one on the left the method should return false (note that any "dead end" must be the beginning or end of any Hamiltonian Path and so any grid with a Hamiltonian Path may contain at most two dead ends).


A grid with a Hamiltonian Path (left) and one with none possible (right)

Assumptions