Anonymous user
Morpion solitaire: Difference between revisions
tidy up sections, improved description of rules
(added proposed requirement) |
(tidy up sections, improved description of rules) |
||
Line 7:
(Proposed additional requirement): Output the game in the form of the pentasol game notation. (see [[Talk:Morpion_solitaire#Game_Notation]]
'''
There are several variations of the game, this task deals with the 5 point "touching" version also known as "5T".
Morpian solitaire is played on a (theoretically) infinite grid. It begins with 36 points marked in a Greek cross:
Line 23 ⟶ 25:
</pre>
* A move is made by adding one point anywhere that creates a new line of 5 points (without spaces) and drawing a line through them. (Moves are
* Any two lines not running in the same direction may cross.
* Any two lines running in the same direction are allowed to touch at the ends but not overlap (i.e. share at most a single point).
* The game ends when you run out of legal moves. (The game score is the number of legal moves played.)
The rules to morpion solitaire are [http://www.morpionsolitaire.com/English/Rules.htm here].
'''Background'''
A short history of the 5T game:
Line 37 ⟶ 46:
For an up to date list of [http://www.morpionsolitaire.com/English/RecordsGrids5T.htm Morpion 5T Records] see here.
The shortest game possible is [http://www.morpionsolitaire.com/English/Limits.htm 20 moves].
The game is NP-hard in the general case and has a huge search space and is a test case for research into searching methods.
Theoretical bounds have been placed on the longest 5T game. The lower bound of 170 and upper bound of either 324 or 704 according to two different papers (see talk page).
| |||