17
$\begingroup$

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:

enter image description here

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): enter image description here

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):

enter image description here

Observations:

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

enter image description here

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

enter image description here

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:

enter image description here

Structure of $H = 4$:

enter image description here

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.

$\endgroup$
5
  • 1
    $\begingroup$ Have you tried for other sizes? $\endgroup$
    – Milten
    Apr 2, 2019 at 7:47
  • $\begingroup$ I lost the Python code, but can point you to a Scratch prototype that gives the results up to 6x6: scratch.mit.edu/projects/281013671 $\endgroup$
    – Kotlopou
    Apr 2, 2019 at 19:16
  • $\begingroup$ I added other sizes now and substantially reworked the question. $\endgroup$
    – Kotlopou
    Jul 13, 2020 at 13:30
  • $\begingroup$ It seems to be almost equal to A135646. I wonder if that has significance, and whether the similarity holds for larger values as well... $\endgroup$
    – Milten
    Jul 15, 2020 at 9:53
  • $\begingroup$ They differ even at $H = 3$ and I cannot see any topical connection. Did you find this by some kind of pattern-matching? $\endgroup$
    – Kotlopou
    Jul 16, 2020 at 7:04

1 Answer 1

10
+100
$\begingroup$

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)$.

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.