Seventh row template problem

Until October 2023, it was an open problem whether there exists a 7th row edge template with a single stone. During October and November 2023, the users Bobson, Comonoid, Mason, and Quasar of the Hex Discord collaborated on finding such a template, and ended up finding three different ones. Curiously, all of these templates are symmetric, although it is possible and quite likely that asymmetric templates also exist.

Discovery of the templates

In chronological order:

Edge template VII-1c

After Eric Demer's discovery of edge template VI1b on October 6, Bobson noticed that this could likely be turned into a single-stone 7th row template. He found the first such pre-template on October 13; it had width 32, but it was not initially known whether it was minimal. Bobson subsequently reduced the width to 23 cells on October 14, and to 21 cells on October 27. Minimality was checked by a collaborative effort using MoHex, and was finally verified on November 8.

Edge template VII-1a

While checking the minimality of edge template VII-1c, Comonoid first noticed on November 4 that KataHex seemed to indicate that the red stone was connected within this carrier. The validity and minimality of the template was subsequently verified using MoHex, and the minimality proof was finished on November 6.

Edge template VII-1b

While checking the minimality of edge template VII-1c, Comonoid first proposed that there might be a width-19 template if the carrier is wide enough. Comonoid, Quasar, and Mason came up with different carriers, and Mason described what turned out to be the final shape of the template on November 4 and proved its validity. Minimality was subsequently verified by a collaboration among several users, and the final case was finished by Quasar on November 17.

Methodology

Validity

The validity of each template was checked using MoHex, in some cases manually supplying the winning move to Mohex. Bobson also checked the validity using the interactive Hex Prover software.

Minimality

Checking minimality is far more work than checking validity. In principle, one must sequentially remove each cell from the carrier (by placing a blue stone in it) and check that the resulting pattern is not connected, i.e., i.e., is a first-player win for Blue. However, due to symmetries and domination, not all cells need to be checked. Specifically, if x dominates y from Blue's point of view, then if removing x from the carrier kept the template connected for Red, then removing y from the carrier would also keep the template connected. Therefore, if minimality has been confirmed with respect to y, then minimality does not need to be checked with respect to x.

For example, to verify the minimality of edge template VII-1a, only the shaded cells needed to be checked:

Specifically, a capture-dominates x, b kill-dominates x, c capture-dominates x, d fillin-dominates y, e kill-dominates d, f capture-dominates y, g kill-dominates y, h capture-dominates y, and each of i–n capture-dominates z. Therefore, if x, y, and z are necessary in the carrier, then so are a–n. The cells on the left do not need to be checked due to symmetry.