Longest path through a rectangular board

Question

The original problem: You have a $H\times W$ board. Your task is to color some tiles white and some black. There must be a unique beginning and end of the white trail and only one way to get from one to the other. Moving is allowed only through edges. Maximise the number of white tiles.

Example $6 \times 8$ solution:

Is there a formula that produces the maximum number of white tiles just from the height and width?

Observations:

Here are values I have found using a depth-first brute-force search (and the formulae below):

8x8 took over two hours to find. The empty spaces in the table are too complex for brute-force.

Here are the differences compared to the tile one to the left (one tile narrower):

Observations:

Odd boards first get simple zig-zag patterns, but this breaks at $7 \times 7$. A naive idea would be:

But this has merely 31 white tiles. The optimal solution has 33:

The formula for $H = 2$ is $\lceil{\frac{3}{2} W}\rceil$, since columns of $2$ and $1$ white tiles alternate. The formula for $H = 3$ is $2 H + 1$ if $H < 6$ and $2 H + 2$ otherwise, since you just get extensions of this:

Structure of $H = 4$:

For every three added tiles of width, there are an additional 8 white tiles. The differences loop after $W = 5$ as $3,3,2$.

Beyond that, backtracking gets more complicated and I cannot find the pre-loop values, or even prove there is a loop.

Answer 1

In graph theory terms, what you are asking for is the longest path formed by an induced subgraph of the $h\times w$ grid graph.

This problem (longest induced path) has been well studied for a slightly different case: the $m$-dimensional cube graph. This is the graph formed by taking all subsets of $\{1,\dots,m\}$ as vertices and connect two subsets if they differ by a single element; it can also be realised as the skeleton of an $m$-dimensional hypercube. The corresponding problem for the $m$-dimensional cube is known as the "snake in the box" problem.

The reason the snake in the box is studied is that it has connections to error-correcting codes. However, getting an exact answer is notoriously difficult. For example, I found a paper by Östergård and Pettersson published in Graphs and Combinatorics (2015) proving that the answer for the $8$-dimensional cube is $98$, and this is the largest case that is known.

The longest induced path problem is studied in more general graphs, where it is known to be NP-complete, i.e. probably computationally difficult. Of course, the grid graph is a very special case, and it may be that there is an easy answer for grids, although I doubt it. I don't know of any work specific to the grid, and it seems like most of the research on the problem in general is about algorithms, rather than finding the values. For example, a very recent paper is "On exact solution approaches for the longest induced path problem", European Journal of Operational Research (2019).

However, we can get an approximate value for the grid, assuming both $h$ and $w$ are large. First, we can get an upper bound as follows. Every white square which is not on an edge is adjacent to at least $2$ black squares, every white square on an edge but not at a corner is adjacent to at least $1$.

Now add up the number of adjacent black squares for every white square. If there are $k$ white squares then there are at least $k-(2w+2h-4)$ squares in the middle, and at most $4$ on corners, meaning the sum is at least $k-4+k-(2w+2h-4)=2k-2w-2h$.

However, the sum counts every black square at most $4$ times (each black square has at most $4$ white neighbours), so there are at least $(k-w-h)/2$ black squares. Since there are $hw$ squares in total we have $k+(k-w-h)/2\leq hw$, i.e. $k\leq\frac{2hw+h+w}{3}$, which is about $2/3$ of the grid. (Formally, $k\leq 2hw/3+O(h+w)$.)

We can get a construction of about this many for $h,w$ large. The idea is to make a diagonal pattern covering almost all the grid (all but a few rows/columns on each side) in which we have two diagonals white and one black in a repeating pattern. Then go round the outside and add black squares as needed to make a zig-zag path through the grid (example below). Since we use $2/3$ of the squares except for a few rows and columns, this has length $2hw/3-O(h+w)$.