Welcome on the Solitaire web page.
What is Solitaire? There are actually many games called that way. It usually comes from the fact that you can play it alone. This one is coming from what in French we call le morpion. The game is played trying to align 5 crosses drawing a line using 4 existing crosses. Only crosses which have not yet been used to draw a line in a given direction (except for the tips), can be used.
The current version of the software ran on a Dual PIII both running at 1Ghz with 1Gb of RAM and 60Gb IDE HD. It generated 1.8Gb of data in about 6 months running 24h a day and found many states as shown in a table below, but was stopped at level 83 (i.e. 83 crosses before to get stuck). This version is "uni-computer" at this time. It would be possible, however, to run it on a beowulf if you have one... Because of the way it is programmed, only one process per level can run at a time. Thus, if you have some 80 nodes you could run one process per level 24h a day (instead of 2 for me!).
At this time I have two main ideas to improve (hopefully) the speed and especially the multi-computer management:
play directory including
84 sub-directories (l0000 to l0083)
and each directory includes one state and one move file.
The state tells us which move to try next and the move
is a copy of the current game as it stands.
Below is a table giving you a list of results as computed
by the count shell script (see the v3 bin
directory). The Level column gives the name
of the level. Note that only 4 were fully completed in
about six months (level 0 to 3). Notice the exponential
number of possibilities: 1, 12, 147, 1213! The States
column gives a count of the *.state files. These
include the current state for a specific move (i.e. m000000.state
is the current state of the move m000000.move).
The state file can be DONE in which case the file is
renamed as *.done and isn't counted in the
States column. The Moves and
Finish is the total number of move files and
the total number of move files which where already checked
out. Note that the number of States plus the
number of Finished is equal to the number of
Moves. The Done column is a count
of the number of states generated at this level. This can
be dramatically higher than the number of moves in the
following state since many moves give equivalent results.
For instance, to find out that there are 12 possible starting
points, the computer generated 29 different game. However,
out of these 29, many are symetrically equal.
Level States Moves Finish Done Last Accessed
l0000 0 1 1 29 09:53:20 - 25 February
l0001 0 12 12 333 17:07:56 - 1 March
l0002 0 147 147 3873 18:10:00 - 1 March
l0003 0 1213 1213 30319 13:58:23 - 2 March
l0004 5139 7794 2655 62690 15:17:24 - 6 April
l0005 17806 19470 1664 37115 10:14:16 - 1 July
l0006 18511 18889 378 7994 15:06:25 - 24 June
l0007 9456 10236 780 15577 19:23:21 - 21 May
l0008 11600 12354 754 14418 19:18:35 - 21 May
l0009 10609 10832 223 4205 19:14:30 - 21 May
l0010 4868 5060 192 3482 10:25:28 - 20 May
l0011 5208 5314 106 1879 19:11:16 - 21 May
l0012 4614 4708 94 1637 17:05:16 - 21 May
l0013 5749 5834 85 1435 20:00:24 - 20 May
l0014 4565 4647 82 1384 19:08:22 - 21 May
l0015 3728 3809 81 1384 19:07:05 - 21 May
l0016 6371 6447 76 1301 19:04:32 - 21 May
l0017 9166 9239 73 1179 19:01:05 - 21 May
l0018 4958 5033 75 1173 18:59:09 - 21 May
l0019 5204 5270 66 975 18:56:37 - 21 May
l0020 4067 4229 162 2248 18:55:09 - 21 May
l0021 2379 2537 158 2051 16:49:17 - 21 May
l0022 1663 1825 162 1994 18:53:58 - 21 May
l0023 1549 1703 154 1884 16:48:51 - 21 May
l0024 1414 1576 162 1963 18:53:22 - 21 May
l0025 1452 1626 174 1969 18:52:50 - 21 May
l0026 1010 1230 220 2412 19:43:42 - 20 May
l0027 1309 1523 214 2240 04:48:24 - 20 May
l0028 1153 1369 216 2206 04:00:00 - 20 May
l0029 882 1151 269 2446 18:51:42 - 21 May
l0030 1013 1330 317 2402 16:47:10 - 21 May
l0031 656 1102 446 2915 03:23:22 - 20 May
l0032 933 1060 127 681 15:34:49 - 18 May
l0033 94 221 127 652 18:15:46 - 16 May
l0034 96 208 112 598 19:42:23 - 20 May
l0035 93 188 95 563 18:50:44 - 21 May
l0036 101 219 118 764 10:11:09 - 15 May
l0037 16 314 298 2935 18:50:36 - 21 May
l0038 1154 1220 66 663 00:09:36 - 17 May
l0039 315 395 80 799 18:50:09 - 21 May
l0040 238 451 213 2182 19:41:40 - 20 May
l0041 971 1174 203 2040 04:46:24 - 20 May
l0042 995 1238 243 2194 03:57:48 - 20 May
l0043 945 1307 362 2980 16:45:30 - 21 May
l0044 1467 1579 112 935 03:21:19 - 20 May
l0045 402 508 106 850 18:49:17 - 21 May
l0046 436 544 108 816 19:40:25 - 20 May
l0047 251 378 127 932 18:49:01 - 21 May
l0048 240 459 219 1496 18:48:53 - 21 May
l0049 326 624 298 1908 16:44:51 - 21 May
l0050 414 624 210 1101 16:44:40 - 21 May
l0051 299 461 162 842 18:48:33 - 21 May
l0052 409 529 120 749 18:48:23 - 21 May
l0053 494 584 90 733 18:48:13 - 21 May
l0054 227 318 91 844 16:44:00 - 21 May
l0055 312 481 169 1907 03:20:07 - 20 May
l0056 912 1136 224 2420 18:47:38 - 21 May
l0057 1190 1527 337 3397 04:43:45 - 20 May
l0058 1437 1538 101 953 04:43:17 - 20 May
l0059 581 698 117 935 19:38:47 - 20 May
l0060 244 408 164 1115 04:43:02 - 20 May
l0061 84 366 282 1604 16:42:23 - 21 May
l0062 5 402 397 1919 18:46:35 - 21 May
l0063 44 451 407 1896 18:46:27 - 21 May
l0064 78 504 426 2250 19:38:17 - 20 May
l0065 302 647 345 1973 04:42:28 - 20 May
l0066 416 632 216 1220 03:18:13 - 20 May
l0067 270 490 220 1243 01:44:26 - 20 May
l0068 0 434 434 2414 18:45:43 - 21 May
l0069 0 738 738 3989 09:55:32 - 23 May
l0070 0 1142 1142 6006 14:04:52 - 23 May
l0071 0 1688 1688 8753 21:33:34 - 23 May
l0072 0 2507 2507 13342 03:29:21 - 26 May
l0073 0 4012 4012 21687 22:02:39 - 28 May
l0074 0 6635 6635 33272 20:55:07 - 4 June
l0075 1744 9681 7937 34452 14:56:26 - 26 June
l0076 1526 9250 7724 26470 10:17:38 - 1 July
l0077 0 6143 6143 15861 20:03:37 - 22 May
l0078 0 2953 2953 6222 17:24:39 - 22 May
l0079 0 1100 1100 2830 16:26:27 - 22 May
l0080 0 610 610 1386 10:56:41 - 22 May
l0081 0 272 272 521 06:42:11 - 22 May
l0082 0 85 85 117 23:26:49 - 21 May
l0083 0 29 29 29 23:25:57 - 21 May
Level States Moves Finish Done Last Accessed
Total number of moves: 228672
Total number of terminals: 62512
A little bit of history... I first played this game when I was
13. For some reason, I felt in love with it and liked it so
much that I decided there should be a way to find out all the
solutions. Since then, I made several attempts to do just that.
The very first version would try to compute all the solutions
at once. It very quickly became clear that you needed a way
to stop the process and restart it. This was version II. However,
version II got stuck at level 4. As we can see in version III,
level 4 isn't finished yet! After 62690 moves from level 4 to
level 5, the computer worked on only 65.93% of the moves
defined at level 4. For
this reason I created this newer (better?) version which would
instead be able to compute any move from any level at any time.
It is very easy to run, though, there are potential problems
if you lose power as the computer is saving a state, it's
unlikely to be so bad since files are very small. A new state
will be saved before the *.state file is updated
thus you may endup computing the same move twice. Not so bad,
right?
This code is, to my point of view, fully mature and should work on your computer under Linux. I successfully compiled it under RedHat 6.2 and 7.1. Other Unix systems may also accept this code with only a very few changes.
At this time I'm thinking of doing a version IV which would allow a large network of computers (without having to run a beowulf) to run Solitaire in order to accelerate the computation of the result. I'm, however, not too sure how to do it yet. So I will only post the analysis here and you will be welcome to send me comments & suggestions.
The Author
Alexis Wilke
Dec 31, 2002