# Morpion solitaire

This is a game that I remember having learnt from my grandparents in my childhood. Initially I didn't know the name. G B has found it to be Join Five (or less ambiguously - Morpion solitaire) with a slightly different starting position.

NOTE: it seems that it's kinda known and this problem formulation has quite good solutions already (http://www.morpionsolitaire.com/English/RecordsGrids5T.htm). I don't know what to do with this thread now honestly.

# Description

The game is played by a single player on a 2-dimensional infinite grid. The grid at the start contains some dots in a cross shape:

A player can create either a horizontal, vertical, or a diagonal (or anti-diagonal) line with the following rules:

• The line must be straight and aligned on the grid.
• The line must span exactly 5 grid points (2 on the ends, 3 in the middle).
• All 5 grid points that the line intersects must have dots on them.
• The new line cannot overlap with an already existing line. But they can intersect and the ends can touch. (ie. intersection of any two lines must not be a line)
• A single dot may be put by the player at any grid point before the line is placed. If the player does so then the line must pass through that point.

A move can be described by a grid point position (cartesian coordinates) and a direction (a number between 0 and 7. 0 - north, 1 - north east, 2 - east, and so on). So 3 numbers. The origin choice is arbitrary, but I suggest using this coordinate system: (An example of sample input at the end)

At the start there is 28 possible moves (12 horizontal, 12 vertical, 2 diagonal, 2 antidiagonal).

An example move:

An example state after 16 moves:

I don't know whether there exists an infinite sequence of valid moves from the start position, but I assume not based on a lot of playing and simulations. Any proofs regarding upper bounds are appreciated.

# Challenge

The challenge is to find the longest possible sequence of valid moves (for a verifier look at the end). The score is the number of moves in that sequence. Higher score is better.

# Tips, help, and resources

A 24x24 board was enough for my random simulations, 32x32 board may be enough for anything possible.

I faintly remember getting scores close to 100 by hand years ago. After billions of random playouts (move uniformly chosen) the best result was 100 consecutive moves:

1 -1 2
1 2 2
1 6 0
-3 5 2
-2 5 0
-5 1 3
-2 -4 2
1 3 1
-5 -1 2
-5 0 1
-5 2 0
0 5 1
-2 0 0
1 -2 3
3 2 0
1 -1 0
-5 2 2
-5 -2 3
-3 3 0
4 3 0
-3 2 3
0 -4 3
-2 0 1
-3 -1 1
-3 -2 2
-1 -3 3
2 2 0
-3 0 1
1 2 1
1 -2 2
1 -5 3
-2 -3 2
1 -4 3
-1 0 0
-3 -2 3
5 2 0
-3 2 1
2 1 2
0 -1 0
0 -1 3
0 0 2
0 1 1
-4 0 2
-6 -2 3
-2 2 1
-2 1 2
0 2 1
-1 5 0
-4 6 1
-3 -3 3
-4 -2 3
-4 2 0
-6 1 2
0 3 0
-7 -2 2
-6 0 1
0 3 2
-7 -2 3
-4 3 2
-6 2 0
-6 1 3
-3 4 2
-3 6 1
1 5 1
-2 2 3
-3 7 0
2 6 0
-1 2 3
-7 3 1
2 5 1
3 6 0
-4 5 1
-3 7 1
-4 6 0
-6 2 3
-6 4 1
-7 3 3
-6 6 1
0 2 3
-6 6 2
-5 6 0
-7 4 2
1 6 2
-7 4 1
-8 3 2
-6 3 3
-6 6 0
-9 2 3
-7 5 2
-7 6 1
-7 6 0
1 2 3
-9 2 2
-9 4 1
1 5 2
1 1 3
4 7 0
1 4 2
5 6 0
1 7 1
Num moves: 100
Board:
o o
|/|\
o-o-o-o-o
/|/|/|X|X \
o o-o-o-o-o o o
/ X|/|X|/|\ \ X
o-o-o-o-o-o-o-o-o-o-o-o-o
\|\|X|X X|X|/|X|X|X|X X|
o o-o-o-o-o o o-o-o-o-o
|X|X|X|X|X|X|X X|X|X|X|
o o o-o-o-o-o-o-o-o-o o
|/|X|X|X X X|X X|X|X| |
o-o-o-o-o-o-o-o-o-o-o-o-o
/|X|X|X|X|X|X|X X|X|/|X|/
o-o-o-o-o-o-o-o-o o o-o-o-o-o
\ /|/|X|X|X|X|X|X|X|X|X|X|/|
o-o-o-o-o-o-o-o-o-o-o-o-o o
/ \|X|X|X|X|X|X|X X|X|X|X|/|
o   o-o-o-o-o-o-o-o-o-o-o-o-o
|\|X|X|X|X|X|X X|X|X|X|\|
o-o-o-o-o-o-o-o-o-o-o-o-o
|/|X|\|X|X /   \|\|X|\|\|
o o-o-o-o-o     o-o-o-o-o
\|X       /    |
o o     o     o


Can you beat that?

C++17 helpful codes (hosted, because they don't fit in an answer, each on godbolt and coliru, you can use them however you like).:

clean, reference code, handles board, move generation, random playouts:

optimized and parallelized version of the above (also prints move sequences), also with a verifier that takes moves from stdin:

edit. an even more optimized version, about twice as fast:

https://godbolt.org/z/_BteMk

place where you can put input to be verified:

https://godbolt.org/z/DJtZBc

example input:

10        # number of moves
-6 2 2    # x, y, direction (0-7)
1 6 0
0 2 2
1 -1 0
1 -1 2
-5 1 3
4 2 0
-5 2 0
-3 -1 1
-2 5 2

• Any proofs regarding upper bounds are appreciated. There exists no sequence of valid moves that can grow the outer boundary of the grid (that is, no infinite moves). You need 4 moves all into empty space in order to create a new 5th valid move, which must be strictly non-parallel to all of the previous 4. This new 5th move cannot generate any moves parallel to the first four, due to both being strictly non-parallel and the no-overlap rule. Commented Dec 5, 2019 at 21:35
• A simpler proof of the finiteness in my opinion is the following: Each point can have up to four lines passing through it, (horizontal, vertical and two diagonal), we can call this line slots. Drawing a line consumes one slot on 4 dots for a total of 4 slots and produces a dot which already has one of it's slots occupied. Therefore every line reduces the total number of slots left by at least 1. When there are less than 3 slots left no further lines can be drawn. This gives an upper bound of 141 moves. Commented Dec 6, 2019 at 5:49
• @WheatWizard A point can be part of up to eight lines, if it is an endpoint for all of them. So assign 8 slots to each point, of which an inner line point uses two. A line with a new point which is an endpoint uses 7 slots and creates 7 new slots. A line with a new point that is an inner point uses 6 slots and creates 6 new ones. That's really tight! Commented Dec 6, 2019 at 13:45
• @Sopel So how long is a diagonal line that passes through 5 total points (two end points and 3 intermediaries)? If it is "four" then the line is defined by how many dots its spanned. If it is "5.657" then it isn't length four and your own example image is wrong (and drawing a line of exactly length 4 would be impossible). Commented Dec 6, 2019 at 14:19
• You might want to rewrite "The line is always of length 4 (2 end points and 3 in the middle)." in a much clearer way, I took this to mean, "The line is always of length 4, which means ...", when it seems to be "The line is always of length 4, and ...". Length 4 is also a confusing concept because under normal assumptions of length our diagonal lines are length $4\sqrt{2}$ (maybe this issue is why I looked to the parentheses for clarification). It also might be worth specifically mentioning that parallel lines can intersect at their endpoints. Commented Dec 6, 2019 at 14:41