Kreski / "Morpion Solitaire"

Standard version

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.
Best results My best result is 152, gif, eps, animation, 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 The game is finite in the sense that the maximum number of moves is bounded. The proof is here. Although the game is finite it is impractical to check all the solutions (the number of different games is estimated as above 1050).

Version with bonus points

Rules - bonus points There is a different set of rules for the game, which allows one to obtain larger number of lines. The only modification is that the point, which is chosen in the given move does not have to belong to the line which is drawn. First you choose a point on the plane and then you draw a line connecting 5 adjacent points. Hence if at the beginning of the move there are 5 adjacent point you may choose a new point (bonus point) anywhere in the plane and then draw a line through the 5 existsing points. When this version is played it is more convenient to decide later where to put bonus points. So it there is a bonus point in the current move you actually do not draw a point on the grid but add it to the rack of bonus points. In this version one may choose a new point in a place where there is a good chance of drawing many lines. This version was described by Krzysztof Loryś ( http://www.oi.edu.pl). Best results Some of the results reported are copied from http://www.oi.edu.pl/old/php/show.php?ac=p171900&module=results&op=krechy ): 169 (Mar 19, 2000), Michał Czuczman, 180 (Apr 03, 2000), Arkadiusz Paterek, 185 (Apr 23, 2000), Andrzej Hoppe, 192 (Jan 23, 2004), Marek Kurcyus 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), ZG, gif, eps, animation,

Version with borrowing bonus points

Rules - borrowing bonus points Here is another problem associated with the "kreski" game. In this problem there are no initial points. The problem is to draw as many lines as possible. The only limitation is that the number of grid points occupied by the lines minus the number of lines should be no more than 36. This version can be seen as a version with bonus points, where initially there are 36 bonus points (and no initial points on the grid). During play one can borrow as many bonus points as one needs. The only requirement is that at the final layout all borrowed bonus points are given back. Note that both versions of the game (standard rules, version with bonus points) satisfy the condition that the number of grid points minus the number of lines is 36 (initially there are 36 points, and in each move one line is added and one point is added). Therefore, the best solution in this porblem is an upper bound on the number of moves in both versions of the "kreski" game. Best results The best solution I know is the one with 227 lines (see the picture to the right), gif, eps. Hence, it seems that the maximum number of lines in the "kreski" game is bounded by 227. However this number is perhaps not a realizable number. For the simpler version of the game (16 initial grid points) the solution with 39 lines is not realizable (see below).

Simpler games - fewer initial points

Rules 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 has 31 lines (gif, eps, animation). The best solution in the version with bonus points is the one with 34 lines (gif, eps, animation). The best solution in the version with borrowing bonus points is the one with 39 lines (gif, eps).

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
  • My old implementation
    • 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,
    • Executable code: SunOS (old, 07.01.2000): for SunOS,
  • There are many other programs for playing this game, the list is available at http://euler.free.fr/morpion.htm.
  • To play the bonus points version you may use the applet at http://www.oi.edu.pl.