Difference between revisions of "Seventh row template problem"
(updating verification status) |
|||
| (6 intermediate revisions by one other user not shown) | |||
| Line 4: | Line 4: | ||
In chronological order: | 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 === | === Edge template VII-1c === | ||
| Line 14: | Line 27: | ||
/> | /> | ||
| − | This template has width 21. | + | 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. | 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. | ||
| Line 38: | Line 51: | ||
For Blue playing a,b,c,d, Red can respond with X,Y,Y,Z respectively. For the rest Red can respond with b. | 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 ( | + | Bobson continued to reduce the size of this pre-template. He first considered the following width 19 carrier (the gray area): |
<hexboard size="7x23" | <hexboard size="7x23" | ||
| Line 44: | Line 57: | ||
edges="bottom" | edges="bottom" | ||
visible="area(a7,w7,w5,u3,r3,p1,n1,j3,g3,c5)" | visible="area(a7,w7,w5,u3,r3,p1,n1,j3,g3,c5)" | ||
| − | contents="R o1 E *:m4 *:n4 S gray:area(c7,u7,u5,s3,r3,p1,n1,j3,i3,e5)" | + | 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, 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 | + | 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 === | === Edge template VII-1b === | ||
| Line 71: | Line 71: | ||
/> | /> | ||
| − | This template has width 19. | + | This template has width 19, and its [[carrier]] has size 90, including the red stone. |
| − | While checking the minimality of [[edge template | + | 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 == | == Methodology == | ||
| Line 79: | Line 79: | ||
=== Validity === | === Validity === | ||
| − | The validity of | + | 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 === | === Minimality === | ||
| Line 85: | Line 85: | ||
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. | 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 | + | For example, to verify the minimality of [[edge template VII1a]], only the shaded cells needed to be checked: |
<hexboard size="7x17" | <hexboard size="7x17" | ||
Latest revision as of 14:25, 1 December 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.
Contents
Discovery of the templates
In chronological order:
Edge template VII-1a
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
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:
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 (the gray area):
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
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:
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.
