Are there topological invariants for this path-finding game?

67 Views Asked by At

There is a game I've seen recently (link; note that I have no affiliation with this game) which involves finding a Hamiltonian path connecting a graph of points, as illustrated below.

blank board ...... filled board

The rules are:

  • Your starting point is fixed (it is the highlighted dot in the first picture).
  • You must form a path connecting all dots on the board, moving only up, down, left or right, and not hitting any dot twice.
  • You can't pass through the black squares.
  • Typically, the endpoint is fixed as the only dot with valency 1.

Solutions to this game are not unique, but I initially conjectured that they were path homotopic (viewing the paths as embedded in $\mathbb{R}^2$ punctured at the locations of the squares). This turns out to not be true, as the following alternative solution to the above board demonstrates:

alt solution

Question: Are there any topological invariants to the solutions of this game?

Here are two more boards with multiple solutions for reference:

b2 ... b2s1 ... b2s2

b3 ... b3s1 ... b3s2