Kreski / "Morpion Solitaire"

Aim of the game The aim of the game is to draw as many lines as possible. The game is played on a rectangular grid. You make a move by drawing a line. At the beginning of a game there are 36 points lying on a cross-like pattern (see picture to the right or check the files: gif, eps). You can draw a line (horizontal, vertical or diagonal) of length 4 connecting four existing points and one new point. A new point (which may be located at the end or in the middle of the line) is added to the set of existing points and may be used in the following moves. At the very beginning you can make 28 different moves and the number of possible moves can become larger as the game proceeds. There are many possible combinations, and it is hard to check them all. If you know a good solution please send me an e-mail.
The best known result An example solution with 148 lines is shown to the right (gif, eps, text). My best result is 152. Recently I learned that this game is known under the name "Morpion Solitaire". The best result is 170 (check http://euler.free.fr/morpion.htm, or http://www.morpionsolitaire.com). It was found by Charles-Henri Bruneau in 1976.
The game is finite Some time ago, I found how to show that the game is finite (meaning that the maximum number of moves is bounded). It seems that the best solution is worse than the one with 205 lines (see the picture to the right) (gif, eps, text) (although I am not sure this is really the case). Hence I believe that the maximum number of lines in the game is bounded by 205 (or some number close to it). However this number is not necessarily a realizable number. For the simpler version of the game (see below) the optimal number (38) is not realizable. And although the game is finite it is impractical to check all the solutions (the number of different finished games is estimated as above 1050).
Simpler version There is an infinite number of versions of the game with different initial layouts of points. One of them is a version with 16 initial points filling a 4x4 square. This game can be solved. For this version there are 1597768 different final layouts of lines, where no more moves can be made. The minimum number of moves is 12, and this could be easily found. The best solutions with 31 lines (gif, eps, text) is shown to the right.

Different rules

• 169 (Mar 19, 2000), Michał Czuczman,
• 180 (Apr 03, 2000), Arkadiusz Paterek,
• 185 (Apr 23, 2000), Andrzej Hoppe,
• 194 (Apr 18, 2000), Mieczysław Pyra,
• 194 (Mar 31, 2000), Maciej Sawitus,
• 196 (Jan 27, 2004), Daniel Górski,
• 197 (Jun 11, 2001), ZG,
• 199 (Sep 3, 2004), found by a computer, using as a hint the one with 197 lines,

How to play

• Use a pencil and a piece of paper (and possibly a rubber if you happen to change your mind and want to undo a move)
• Play on a computer
  • Advantages
    • you can easily undo as many moves as you want,
    • computer may show you all possible moves,
    • computer can help you in finding a better solution.
  • Disadvantages
    • hard to play at school
  • Source file (xview header files necessary - not supplied): hatch.C
  • Executable code
    • RedHat linux (old, 07.01.2000): for linux, xview libraries: xview-3.2p1.4-6.i386.rpm,
    • SunOS (old, 07.01.2000): for SunOS,
    • there are many programs for playing this game, the list is available at http://euler.free.fr/morpion.htm.
    • to play a game with rules proposed by K. Loryś (see above) you may use the applet at http://www.oi.edu.pl/php/show.php?ac=p240100.