View source for 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 forums|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 ===

<hexboard size="7x17"
  coords="none"
  edges="bottom"
  visible="area(a7,q7,q5,p3,n1,j1,f3,c5)"
  contents="R l1"
  />

This template has width 17, and its [[carrier]] has size 84, including the red stone.

While checking the minimality of [[edge template VII1c]], 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 ===

<hexboard size="7x21"
  coords="none"
  edges="bottom"
  visible="area(a7,u7,u5,s3,q3,o1,m1,i3,g3,c5)"
  contents="R n1"
  />

This template has width 21, and its [[carrier]] has size 98, including the red stone.

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:

<hexboard size="7x23"
  coords="none"
  edges="bottom"
  visible="area(a7,w7,w5,u3,r3,p1,n1,j3,g3,c5)"
  contents="R o1 1:n3 S blue:area(j7,w7,w5,u3,r3,p1,o1,n2,m4)"
/>

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

<hexboard size="7x23"
  coords="none"
  edges="bottom"
  visible="area(a7,w7,w5,u3,r3,p1,n1,j3,g3,c5)"
  contents="R o1 E a:n2 b:n3 c:m4 d:l5 e:m5 f:k6 g:l6 h:j7 i:k7 j:l7 X:o2 Y:m2 Z:n4"
/>

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 (the gray area):

<hexboard size="7x23"
  coords="none"
  edges="bottom"
visible="area(a7,w7,w5,u3,r3,p1,n1,j3,g3,c5)"
  contents="R o1 E *:m4 *:n4 +:(a7 b6 c5 e4 g3 w7 w6 w5 v4 u3) S gray:area(c7,u7,u5,s3,r3,p1,n1,j3,i3,e5)"
  />

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 (removing + cells), 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 ===

<hexboard size="7x19"
  coords="none"
  edges="bottom"
  visible="area(a7,s7,s5,p2,n1,l1,i2,c5)"
  contents="R m1"
  />

This template has width 19, and its [[carrier]] has size 90, including the red stone.

While checking the minimality of [[edge template VII1c]], Comonoid first proposed that there might be a width-19 template if the carrier has more vertical space. 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 all templates was checked by Mason and Quasar using [[MoHex]], in some cases manually supplying the winning move to Mohex. Bobson also checked the validity of the three templates 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 VII1a]], only the shaded cells needed to be checked:

<hexboard size="7x17"
  coords="none"
  edges="bottom"
  visible="area(a7,q7,q5,p3,n1,j1,f3,c5)"
  contents="R l1 S blue:area(l2,k3,i7,o7,n6,o5),n1,p3,q7
            E a:m1 b:m2 c:n2 d:o2 e:n3 f:o3 g:o4 h:p4 i:p5 j:q5 k:o6 l:p6 m:q6 n:p7 x:n1 y:p3 z:q7"
  />
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&ndash;n capture-dominates z. Therefore, if x, y, and z are necessary in the carrier, then so are a&ndash;n. The cells on the left do not need to be checked due to symmetry.


[[Category: Edge templates]]