Morpion solitaire: Difference between revisions
Content added Content deleted
(added proposed requirement) |
(tidy up sections, improved description of rules) |
||
| Line 7: | Line 7: | ||
(Proposed additional requirement): Output the game in the form of the pentasol game notation. (see [[Talk:Morpion_solitaire#Game_Notation]] |
(Proposed additional requirement): Output the game in the form of the pentasol game notation. (see [[Talk:Morpion_solitaire#Game_Notation]] |
||
''' |
'''Playing Morpion Solitaire''' |
||
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: |
Morpian solitaire is played on a (theoretically) infinite grid. It begins with 36 points marked in a Greek cross: |
||
| Line 23: | Line 25: | ||
</pre> |
</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 |
* 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 commonly marked with the number of the move for visual clarity. Creating a record of the game in game notation is a better way to validate a game.) |
||
* 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: |
A short history of the 5T game: |
||
| Line 37: | Line 46: | ||
For an up to date list of [http://www.morpionsolitaire.com/English/RecordsGrids5T.htm Morpion 5T Records] see here. |
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 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). |
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). |
||