11
\$\begingroup\$

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:

enter image description here

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)

enter image description here

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

An example move:

enter image description here

An example state after 16 moves:

enter image description here

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:

http://coliru.stacked-crooked.com/a/1de13a65522db030 https://godbolt.org/z/zrpfyU

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

http://coliru.stacked-crooked.com/a/b991b7c14aaf385e https://godbolt.org/z/vFwHUe

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
Improve this question
\$\endgroup\$
20
  • 5
    \$\begingroup\$ 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. \$\endgroup\$
    – Draco18s no longer trusts SE
    Dec 5, 2019 at 21:35
  • 5
    \$\begingroup\$ 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. \$\endgroup\$
    – Wheat Wizard ♦
    Dec 6, 2019 at 5:49
  • 3
    \$\begingroup\$ @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! \$\endgroup\$
    – Christian Sievers
    Dec 6, 2019 at 13:45
  • 1
    \$\begingroup\$ @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). \$\endgroup\$
    – Draco18s no longer trusts SE
    Dec 6, 2019 at 14:19
  • 4
    \$\begingroup\$ 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. \$\endgroup\$
    – Wheat Wizard ♦
    Dec 6, 2019 at 14:41

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.