Difference between revisions of "Seventh row template problem"

Revision as of 13:25, 18 November 2023

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-1a

This template has width 17.

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-1c

This template has width 21.

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 of arbitrary width using HexProver on October 13. The pre-template was soon reduced to width 23 on October 14, as he realized that using edge template VI1b was not necessary.

To explain how the width 23 pre-template works, notice that Red can try to connect the 7th row stone to the edge with a variant of edge template V1b from both sides:

Thus Blue has these possible blocks (a~j, mirrored positions are removed).

For Blue playing a,b,c,d, Red can respond with X,Y,Y,Z respectively. For the rest Red can respond with b.

Bobson continued to reduce the size of this pre-template. He first considered the following width 19 carrier (contained in the width 23 pre-template):

MoHex shows that every intrusions other than * are solvable within this carrier. On the other hand, Bobson found that intrusions at * can be solved within width 21, so the pre-template was then reduced to width 21 on October 27. The minimality was checked by a collaborative effort using MoHex (patched version made by Comonoid and Quasar so that it can be run on a 23×23 board), and was finally verified on November 8.

Edge template VII-1b

This template has width 19.

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 VII1b and VII1a was checked by Mason using MoHex, in some cases manually supplying the winning move to Mohex. Bobson also checked the validity of VII1c and VII1b using the interactive HexProver 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.