Given an n by m grid of vertices, draw a line between the vertices starting at a vertex
vand finishing at another vertexw, visiting each exactly once.
This utility implements algorithms for the existence & construction of a Hamiltonian path in an arbitrary grid graph.
For more details, see:
- Problem specification: A more informal, intuitive look at the problem
- Hamilton Paths in Grid Graphs: The paper which originally formalized, generalized, and explored the problem
Draw a Hamiltonian path between two vertices in a grid graph G(n, m)
Usage: grid-solver.exe [OPTIONS]
Options:
--width <WIDTH> Width of the grid
--height <HEIGHT> Height of the grid
--start-x <START_X> Start vertex x coordinate
--start-y <START_Y> Start vertex y coordinate
--end-x <END_X> End vertex x coordinate
--end-y <END_Y> End vertex y coordinate
-h, --help Print help
-V, --version Print version
At a recent IBM potluck, employees were presented with the following toy problem - draw a straight line through all points in the below grid starting at the start point and ending at the end point.
These instructions were vague as they did not explicitly state the validity of certain moves. Solutions were found both involving moving diagonally between points, and leaving the grid. However, these were both considered "exceptions"; the ideal solution would only utilize moves contained within the graph between immediately adjacent points in the right, left, up, and down directions. However, no such solution could be found by participants.
I set off to write a program that would solve any general grid problem like this one. In the process, I discovered that the problem had been formalized and thoroughly explored in Hamilton Paths in Grid Graphs. I then decided to implement the algorithms described in this paper, and to communicate the results discussed in the paper (which I think are quite interesting) in this repository.