4x4 grid with the shortest longest path

Question

This is an extension of this beautiful puzzle.

This time your task is to find the hardest 4x4 grid. In particular, find a 4x4 grid containing every number from 0 to 9 at least once, such that the longest path that visits distinct numbers is as short as possible. The path can start at any number and can move horizontally or vertically, but not diagonally. You can use a computer for this.

Answer 1

I got the longest path down to

5

and I don't think it can be improved upon.

1 2 0 3
4 0 5 0
0 6 0 7
8 0 9 A

(The A can be any number, including a previously unused one.)

If it were only the numbers 1-9, then choosing one of the digits as "padding" and making a checkerboard with it, we could sprinkle the other digits in between, for a result of three.

However, we have an extra digit, so we must have at least one group of 2 adjacent non-padding digits. Sadly, there doesn't seem to be any configuration for fitting 9 squares in non-adjacent groups of maximum size 2 onto a 4x4 grid.

Therefore, we must have at least 1 "island" of three non-padding squares, and since we cannot isolate it completely (would need a double layer of padding), the above solution seems optimal.

(Having repeats of some non-padding digits isn't going to help, since turning one of those duplicates into the padding digit cannot make the longest path longer than it was before.)

Answer 2

Proof of optimality of @Bass's solution:

Step 1: Properties of half boards (2x4 or 4x2 sub boards)

If a half board has 7 or 8 distinct numbers, obviously paths of length >= 5 exist.

If it has 6 distinct numbers, then: If either row (wlog the long side is horizontal) has 4 distinct numbers we are done. Otherwise each has 3 with no overlap between the rows. If either row has its duplicate not in the centre it is easily seen that a 5 path exists. The only configuration that does not allow a 5 path is therefore abbc / deef

Step 2: Cases

Case 1: The central square has 4 distinct numbers.

Then since there are only 4 non adjacent squares (the 4 corners) one of the adjacent squares must contain a 5th distinct number and a 5 path exists.

Case 2: The central square has repeat elements.

If we split the board in half at least one half (of all 4(!) halves possible) must contain 6 distinct numbers. By the properties of half boards we are done unless it has abbc / deef configuration. But then also one of the orthogonal halves must be in this configuration. Taken together: ..ab / ..cd / eccd / fggh.

In particular, the top right and bottom left 2x2 sub boards have 4 distinct numbers each. As there are 2 unused numbers left and only 1 not yet determined square that is not adjacent to at least one of these sub boards we are done.