# Minimize the longest King chain on a 6x6 ternary grid

This puzzle is an extension of this one: Minimize the longest King chain on a 5x5 binary board

Given a grid filled with numbers, we define a King chain to be a path on the grid such that:

1. The path can be traversed with chess King's moves (moving to one of 8 adjacent cells at a time),
2. The numbers on the path are all equal, and
3. The path does not visit any cell more than once.

The length of a King chain is the number of cells visited by the King.

Can you find a 6x6 grid filled with zeros, ones and twos, such that every pair of cells with the same number are connected via some King chain, and the longest King chain has length 7?

• Do you have reason to believe that there is a 'nice' solution to this? If not, this seems more like a computer programming challenge than a puzzle. – Deusovi Feb 24 at 0:49
• Yes, but people's tolerance of questions that skirt the lines of "puzzle" versus "programming problem" generally decreases as more are posted. Now that we know the previous one had no 'nice' solution, I think it is much closer to "programming problem" than "puzzle". It was unclear at the start, though. This question (and the similar one you asked at about the same time) seem to just be making it harder, meaning it is even less likely that it has a 'nice' solution. – Deusovi Feb 24 at 1:00
• @Albert.Lang I was responding to this conversation and the other at the same time; in the other, they said they had an arrangement that might be optimal but no proof. Based on the other question (as well as previous conversations with them about optimization questions), I had assumed that they meant "many options were tried and this seemed to be the best, but there isn't necessarily an airtight proof". I was also trying to talk about [...] – Deusovi Feb 24 at 5:54
• I have modified the puzzle so it is now asking for a specific length, which I know is possible to achieve. This should make it more of a puzzle. – Dmitry Kamenetsky Feb 25 at 0:39
• Looks much better! – justhalf Feb 25 at 6:39

EDIT: All solutions up to mirror symmetry, rotation, colour permutation found by brute force:

End of EDIT.

One possibility (I write X,O,+ for 0,1,2):

    + X + O X X
O + X O X O
+ O X X O O
+ X O O X X
+ O + X O X
O + O X O O


A bit on how this was found:

To cover as much as possible with one path as short as possible we want it to branch:

Here is one promising pattern (left core pattern, right with example set of subbranches)

    . . . . . .     . . . O . O
O . . . . O     O . . O . O
. O . . O .     . O . . O .
. . O O . .     . . O O . .
. O . . O .     . O . . O O
O . . . . O     O . O . . O


We can neatly fit two of those:

    X . . . . X
O X . . X O
. O X X O .
. X O O X .
X O . . O X
O . . . . O


Now the centre is blocked we can reasonably expect the third colour to cover maybe half the grid but not all. The other half we need to cover using only X and O. This can be done symmetrically:

    X . X O X X
O X . O X O
. O X X O O
. X O O X X
X O . X O X
O . O X O O


It remains to connect the leftover area. This can be done by small adjustments that break symmetry

    . X . O X X
O . X O X O
. O X X O O
. X O O X X
. O . X O X
O . O X O O


• Beautiful work. Well done! – Dmitry Kamenetsky Feb 26 at 3:32
• @DmitryKamenetsky I've added a picture of what I believe are all 315 distinct solutions. – Albert.Lang Feb 26 at 4:59

It feels like this can be improved but the best I've been able to do so far is

8

As follows

2 2 2 2 2 2
2 0 1 0 1 2
1 0 1 0 1 0
1 0 1 0 1 0
0 1 0 1 0 1
0 1 0 1 0 1


• Great start. See my modification to the puzzle. I am now asking for length 7, which I know is possible. – Dmitry Kamenetsky Feb 25 at 0:40