Le Morpion Solitaire

Achim Flammenkamp, Departments of Mathematics, University Bielefeld

created 2003–Mar–19, updated 2008–Feb–08

There is a common known solitaire game in France: le Morpion. It is played on a checkered piece of paper with a pencil. At the beginning of the game the paper contains a so called Maltesian Cross consisting of 36 marked points on its grid. Your aim is to mark as many as possible further points on this grid. A new point can only be marked, if either a line segment of length five in one of the two diagonal directions or the two orthogonal directions relative to the grid could be chosen to cover this new point, provided then this line segment is completely covered by marked points and at most one single marked point of it is already covered by other line segments.

We like to put these conditions in a precise mathematical model: Given the grid ℤ^{2}, then we denote by P_{0} the special start configuration

{(x, y) ∈ ℤ^{2} : 0 ≤ x, y ≤ 9, λ(x, y)}

where λ is the characteristic boolean function of the start configuration which is defined as

λ(x, y) = \{ \begin{matrix}3 |̸ x , & 3 |̸ y : & FALSE \\ 3 |̸ x , & 3 | y : & 2 | ⌊\frac{x}{3}⌋ ≠ 3 | ⌊\frac{y}{3}⌋ \\ 3 | x , & 3 |̸ y : & 3 | ⌊\frac{x}{3}⌋ ≠ 2 | ⌊\frac{y}{3}⌋ \\ 3 | x , & 3 | y : & 3 | ⌊\frac{x}{3}⌋ ∨ 3 | ⌊\frac{y}{3}⌋ \end{matrix}

using the binary boolean divide-operator | . Then we have r := |P_{0}| = 36. Next we define the set L of all line segments of length five to be

{ ((x−id, y−it))_{i∈{−2,−1,0,1,2}} : x, y ∈ ℤ (d, t) ∈ {(1, 0), (0, 1), (1, −1), (1, 1)} }

.

Now we search for an as long as possible sequence ((p_{i}, ℓ_{i}))_{i∈{1,2,...,n}} of pairs of points p_{i} ∈ ℤ^{2} and line segments ℓ_{i} ∈ L satisfying the following three conditions ∀ i ∈ {1, 2, …, n}:

i p_{i} ∉ P_{0} , ∀ j < i : p_{i} ≠ p_{j}

ii p_{i} ∈ ℓ_{i} , ∀ j < i : |ℓ_{i} ∩ ℓ_{j}| ≤ 1

iii ∃ i_{1}, i_{2}, i_{3}, i_{4}, i_{5} ∈ {1, 2, …, i} : ℓ_{i} = (p_{i_{1}}, p_{i_{2}}, p_{i_{3}}, p_{i_{4}}, p_{i_{5}})

Condition (i) means: add each move a further, previously unmarked point to the grid. Condition (ii) means: this point must be covered by a new line segment, but the new line segment is not allowed to have more than one point in common with any other line segment. and condition (iii) says that the new line segment must be covered completely by marked points.

An open problem is still to determine the maximal possible value of n. In this paper we like to show that such an n exists indeed and we give an upper bound on the maximum n.

For this purpose we define for every k ≤ n an evaluation function f_{k} on ℤ^{2} depending on the set P_{i} := P_{0} ∪ {p_{i}}_{i∈{1,2,...,k}} and the set {ℓ_{i}}_{i∈{1,2,...,k}} of the points and line segments of our sequence ((p_{i}, ℓ_{i}))_{i∈{1,2,...,n}}. To do this we need the for all ℓ ∈ L the notation of

ℓ^{∗} := (p_{2}, p_{3}, p_{4}) if ℓ = (p_{1}, p_{2}, p_{3}, p_{4}, p_{5})

which is simply the middle part consisting of the 3 inner points of any line segment.

Now we define for every k ≤ n, each ((p_{i}, ℓ_{i}))_{i∈{1,2,...,n}} and every q ∈ ℤ^{2}

f_{k}(q) = 8δ_{q∈P_{k}} − ∑_{i∈{1,2,...,k}} δ_{q∈ℓ_{i}} − ∑_{i∈{1,2,...,k}} δ_{q∈ℓ_{i}^{∗}}

This implies that holds

∀ k ∈ {1, 2, …, n} ∀ q ∈ ℤ^{2} : 0 ≤ f_{k}(q) ≤ 8

with the lower bound is due to the fact that the line segments have 4 possible directions and for each direction there is either at most one full cover by the middle of a line segment or two half covers by line ends. Moreover, the fact that each further point p_{i} adds 8 and each corresponding line ℓ_{i} decreases certain f_{k} by 5 + 3, we get — summing f_{k} up over the whole grid —

∀ k : ∑_{q∈ℤ^{2}} f_{k}(q) = ∑_{q∈P_{0}} 8 = 8r

which is an invariante for each k and any sequence.

A point q ∈ P_{k} for whichs holds f(q) = 0 must be saturated in all 4 directions and must be an inner point of the set P_{k}. Thus the points with f > 0 must contain at least the margin points of the set because these can’t be saturated completed in all 4 directions by line segments.

Therefore the set P_{k} ⊂ ℤ^{2} should have a border measure as low as possible to maximize n. This leads immediately to a simple upper bound: Giving 8rmany border points for a subset S the maximization of |S| means S must be at least a convex set and because it is a subset in ℤ^{2} which points are created by line segments in only 4 possible directions it must be a convex 2·4 -gon, namely an octagon. Trivially an octagon has 8 edges, so the fullsymmetric octagon with side length r + 1 has exactly 8r border points and a total number of 7r^{2} + 4r + 1 points.

This rough estimation can be improved by refinement, still assuming we can cover the inner points of the optimal convex octagon perfectly, such that only near the margin of the octagon f > 0. In detail look at a typical corner of such an octagon:

\begin{matrix}. & . & . & . & . & . & . \\ . & . & . & . & . & . & . \\ . & . & . & 4 & 3 & 3 & 3 \\ . & . & 3 & 1 & 0 & 0 & 0 \\ . & 3 & 1 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}

Here a dot . indicates a point q ∉ P, having f(q) = 0, else the value f(p_{i}) is shown. Assuming the horizontal and vertical diameters of the octagon to be b_{1} and b_{2} and the four corner cut-off-sizes to be a_{1}, a_{2}, a_{3}, a_{4} ≤ min{b_{1}, b_{2}}, we get the condition

3(2b_{1} + 2b_{2}) − 2(a_{1} + a_{2} + a_{3} + a_{4}) − 4 ≤ 8r  (1)

for the border weight.

Under this condition we have to maximize

b_{1}b_{2} − ∑_{j∈\{1,2,3,4\}} \frac{a_{j}(a_{j} + 1)}{2}  (2)

the total number of points in respect to b_{1}, b_{2}, a_{1}, a_{2}, a_{3}, a_{4}. Without loss of generality we may assume that b_{1} ≤ b_{2} and a_{1} ≤ a_{2} ≤ a_{3} ≤ a_{4}. Because of the special form of the restriction and the objective function we know that for the maximum must hold b_{1} ≤ b_{2} ≤ b_{1} + 1 and a_{1} ≤ a_{4} ≤ a_{1} + 1. So, renaming a_{1} to a and b_{1} to b, we rewrite the restriction to

12b + 6β − 8a − 2σ − 4 ≤ 8r

with b_{2} − b_{1} = β ∈ {0, 1} and ∑_{j} a_{j} − a = σ ∈ {0, 1, 2, 3} and have to maximize

b^{2} + βb − (a + 1)(2a + σ)

in respect to b, β, a, σ. Because σ and a can be used to get equality in the restriction while at most increasing the objective function, we get with the “active” restriction

a = a(b, β) = ⌊\frac{6b + 3β − 2 − 4r}{4}⌋ ≥ 0

and

σ = 6b + 3β − 2 − 4r − 4a .

Substituting a and σ in the objective function, keeping in mind that 6b + 3β ≥ 4r + 2 must hold, we yield

max_{b,β} b^{2} + βb − (a(b, β) + 1)(6b + 3β − 4r − 2 − 2a(b, β))

For r = 36, the maximum value 741 is attained with b = 31 and β = 0, implying a = 10 and σ = 0.

Remark: If we would drop the requirement that a_{1}, a_{2}, a_{3}, a_{4} and b_{1} and b_{2} must be integers, we could approximate the solution by knowing that in the maximum must hold a_{1} = a_{2} = a_{3} = a_{4}, b_{1} = b_{2} and the restriction 6(2b) − 8a − 4 ≤ 8r must hold with equality. Putting this together, we have to maximize the term b^{2} − \frac{1}{2}((3b − 2r)^{2} − 1) in b, which means that 2b − (3b − 2r)3 = 0 must hold. Then we would get for the optimal b the value \frac{6r}{7} and the maximal value \frac{4r^{2}}{7} + \frac{1}{2}, resulting in the case r = 36 in a maximal value of 741.0714 … as good as our bound on n in the exact all integer estimation.

To get a better bound we like to estimate the size of P_{n} better. The main idea is to use the alignment restriction of the line segments (of length 5). In our model each point q has ”base-costs” of 8 which can be decreased by line segments covers. Therefore our aim is to cover as much as possible points with two lines chosen from the four possible directions to push f_{k}(q) down to 0 for each marked point. Denote the horizontal diameter, this is the maximal number of lines orthogonal to the x-axis to cover P_{n}, again by b_{1} and the vertical diameter, the maximal number of parallel lines to the x-axis to cover P_{n}, with b_{2}. Similar let the diameter in the two diagonal directions be d_{1} and d_{2}. Then we get a to (2) equivalent formula for the number of points covered in all four directions to be

b_{1}b_{2} − ⌊\frac{(b_{1} + b_{2} − d_{1})^{2}}{4} ⌋ − ⌊\frac{(b_{1} + b_{2} − d_{2})^{2}}{4} ⌋  (3)

k + 1 successive line segments lying on the same line overlap only at their end points and thus cover 4(k + 1) + 1 points, causing a waste of at least 2 for each such line regarding their ∑_{q} f_{k}(q). Furthermore because of the alignment restriction modulo 4, we must have an average excess of \frac{1}{4} ∑_{i=0}^{3} i each independent line direction. Because exactly 2 of the 4 directions are independent, we get at least for the lines in the other 2 directions these costs for the miss-aligment. Each point in this excess, which can’t be covered gives a further costs of 2. Trying to avoid mis-alignment on the first and last lines of each set of parallel line-covers can save at most 3/2 for each set, but on the other hand we have to pay 2 · 2 due to the fact that no line of length 1 is availible for each such set of paralle line-covers which out-weights this small win – so we neglect this small effect. Because d_{1}, d_{2} ≥ max{b_{1}, b_{2}} we can put all together to the condition

2(b_{1} + b_{2} + d_{1} + d_{2}) + 2(αb_{1} + (3 − α)b_{2}) ≤ 8r 0 ≤ α ≤ 3  (4)

Maximizing (3) under the asssumption b_{1} ≤ b_{2}, results in the non-integer case in the unique solution

b_{1} = \frac{3}{8}r b_{2} = \frac{6}{8}r d_{1} = d_{2} = \frac{7}{8}r α = 3

which give the maximal value of at most \frac{r^{2}+2}{4}. The all integer solution for our case r = 36, give a maximal value of 324 with the two different solutions b_{1} = 14, b_{2} = 26, d_{1} = d_{2} = 31, α = 3 and b_{1} = 13, b_{2} = 28, d_{1} = d_{2} = 32, α = 3 — for each solution (4) is active.

The current record of n = 170 of a morpion-sequence was set by Denis Excoffier in September 2000. Because always p_{i} ∈ ℓ_{i} we may give ℓ_{i} − p_{i} inplace of ℓ_{i}. To get an even more compact list of these pairs, the line segment can be coded unique as a difference Δ_{i} of its center point from p_{i} and its direction. The four possible directions (1, 0), (0, 1), (1, −1) and (1, 1) are representated as − , | , / and \ respectively.

Now the sequence of pairs p_{i}, Δ_{i} for this record configuration follows:

i  p_{i} Δ_{i}  i  p_{i} Δ_{i}  i  p_{i} Δ_{i}  i  p_{i} Δ_{i}
1 (0,2) 0|  2 (2,0) -2−  3 (2,2) 0/  4 (3,4) 0|
5 (4,3) 2−  6 (4,6) 2−  7 (6,4) 0|  8 (3,5) 0|
9 (5,3) -1− 10 (5,6) -1− 11 (6,5) 0|  12 (2,4) 0\
13 (4,2) 0\ 14 (1,2) -1− 15 (2,1) 0|  16 (-1,4) -2/
17 (4,5) 1\ 18 (5,4) 1\ 19 (1,4) 0− 20 (2,7) 1\
21 (1,5) 0|  22 (4,1) 1/ 23 (-1,7) -2/ 24 (4,4) 0|
25 (4,8) 2\ 26 (4,7) 0|  27 (7,4) 2− 28 (2,5) 0\
29 (2,9) -2/ 30 (5,2) 0\ 31 (-1,5) -2− 32 (2,8) 0|
33 (5,1) 0|  34 (7,0) 2/ 35 (1,7) 0\ 36 (5,5) 1/
37 (7,-1) 2/ 38 (7,1) 2− 39 (8,4) 2\ 40 (0,7) -1−
41 (0,8) -2/ 42 (7,2) 0|  43 (7,5) 2− 44 (7,7) 2\
45 (8,0) 2/ 46 (-1,8) -2/ 47 (4,-1) -2\ 48 (5,7) 0−
49 (8,2) 2− 50 (-1,6) 0|  51 (1,8) 0− 52 (2,10) -2/
53 (5,8) 0| 54 (8,1) 0| 55 (10,4) 2\ 56 (0,9) -2/
57 (3,10) -2/ 58 (7,8) 2− 59 (9,0) 2/ 60 (11,4) 2−
61 (0,10) 0| 62 (1,9) -1− 63 (7,9) 0| 64 (10,0) 2−
65 (1,10) 0|  66 (8,9) 2− 67 (8,10) 2\ 68 (9,1) 1/
69 (4,10) 2− 70 (9,2) 0|  71 (9,10) 2\ 72 (3,11) -2/
73 (10,1) 2/ 74 (3,12) 0|  75 (4,12) 2\ 76 (11,1) 2−
77 (2,11) 1\ 78 (4,11) 0|  79 (10,2) 1/ 80 (2,12) 0|
81 (5,10) 0/ 82 (5,12) 2\ 83 (10,3) 0|  84 (11,3) 2\
85 (5,11) 0|  86 (6,12) 2− 87 (12,2) 2/ 88 (12,5) 2\
89 (6,11) 2− 90 (7,13) 2\ 91 (11,2) 1− 92 (6,10) 0|
93 (7,12) 2\ 94 (8,5) -1/ 95 (11,5) 0|  96 (7,10) 1−
97 (8,8) 2/ 98 (10,5) 1− 99 (7,11) 0| 100 (8,7) 0|
101 (9,8) 2/ 102 (8,12) 2\ 103 (9,7) 0| 104 (12,3) 2/
105 (8,11) 0| 106 (10,8) 2\ 107 (13,3) 2− 108 (9,9) 1/
109 (9,12) 2\ 110 (11,8) 2− 111 (14,4) 2\ 112 (9,11) 0|
113 (10,7) 1\ 114 (10,9) 1/ 115 (10,6) 0| 116 (10,11) 2−
117 (11,7) 2− 118 (12,4) 2/ 119 (12,8) 2\ 120 (12,6) 0|
121 (11,6) 1− 122 (13,5) 1/ 123 (11,9) 0| 124 (12,7) 2\
125 (13,4) 2/ 126 (10,10) 1/ 127 (12,9) 2− 128 (14,5) 2\
129 (15,4) 2− 130 (10,12) 0| 131 (11,11) 2\ 132 (12,10) 0|
133 (13,6) 0/ 134 (15,5) 2− 135 (11,10) 1− 136 (11,12) 2−
137 (13,7) 0| 138 (11,13) 0| 139 (12,11) 2\ 140 (13,8) 2/
141 (14,6) 1/ 142 (12,14) 2\ 143 (15,7) 2\ 144 (14,7) 1−
145 (14,8) 0| 146 (15,8) 2− 147 (15,9) 2\ 148 (15,6) 0|
149 (16,9) 2\ 150 (16,6) 2− 151 (13,9) -1/ 152 (14,9) 0−
153 (13,10) 0/ 154 (13,11) 0| 155 (14,11) 2− 156 (14,12) 2\
157 (14,10) 0| 158 (15,12) 2\ 159 (12,12) -1/ 160 (12,13) 0|
161 (13,12) 0− 162 (13,14) 2\ 163 (15,10) 1/ 164 (15,11) 0|
165 (16,10) 2− 166 (16,11) 2\ 167 (13,13) -1/ 168 (16,12) 2\
169 (13,15) 0| 170 (16,13) 0|