Solver for solitaire

A script to deterministically find a solution for the game solitaire.

It can also be used for an exaustive search.

Prerequisites

The script was developed and tested with GNU/Octave 10.3.0 on CachyOS. The Octave packages parallel and communications are used. It should work with any recent version of Octave.

Usage

The script play_solitaire.m calculates the path data (stored as P.dat) and visualizes 100 random solutions as png-figures in the subfolder solutions.

As the default path data file (P.dat) is checked in, the script by default does not re-calculate the path data but uses the provided data. In order to re-calculate the path data, just delete the path data file (P.dat).

The width of the search window can be changed in the script. By default, only the 10000 most complex nodes are propagated. For an exaustive search, set it to inf.

For an exaustive search, the script uses more than 32GB of memory. On a system with a Ryzen 9 9900X CPU and 64GB of DDR5-6000 RAM, it took about an hour to complete the exaustive search.

Explanation

The default field has 33 tokens or "balls". Hence, all possible configurations (ie game states) can be encoded by 33bit. The game field itself is encoded as a matrix.

Two functions are used to map from game state to a number and vice versa:

• field2num
• num2field

The start field is:

0   0   1   1   1   0   0
0   0   1   1   1   0   0
1   1   1   1   1   1   1
1   1   1  -1   1   1   1
1   1   1   1   1   1   1
0   0   1   1   1   0   0
0   0   1   1   1   0   0

where 1 means that a token is present, -1 indicates that a token is missing, and 0 that the location is not available in the game.

This specific field, for example, is mapped to the number 8589869055. This mapping allows a very memory efficient encoding of the game states.

A propagation function is used to get the next possible game states from a current state:

• step

For example, step(8589869055) gives us the next game states:

• 8589869055 --> 8589934063
• 8589869055 --> 8313110527
• 8589869055 --> 8589885439
• 8589869055 --> 8589541375

We can check num2field(8589934063):

0   0   1   1   1   0   0
0   0   1   1   1   0   0
1   1   1   1   1   1   1
1   1   1   1  -1  -1   1
1   1   1   1   1   1   1
0   0   1   1   1   0   0
0   0   1   1   1   0   0

And num2field(8313110527):

0   0   1   1   1   0   0
0   0   1   1   1   0   0
1   1   1   1   1   1   1
1  -1  -1   1   1   1   1
1   1   1   1   1   1   1
0   0   1   1   1   0   0
0   0   1   1   1   0   0

And num2field(8589885439):

0   0   1   1   1   0   0
0   0   1   1   1   0   0
1   1   1   1   1   1   1
1   1   1   1   1   1   1
1   1   1  -1   1   1   1
0   0   1  -1   1   0   0
0   0   1   1   1   0   0

And num2field(8589541375):

0   0   1   1   1   0   0
0   0   1  -1   1   0   0
1   1   1  -1   1   1   1
1   1   1   1   1   1   1
1   1   1   1   1   1   1
0   0   1   1   1   0   0
0   0   1   1   1   0   0

Each of these fields/game states can in turn be further propagated, until no moves are possible anymore.

For example, the next steps would result in the following states:

• 8589934063 --> 8581480431
• 8589934063 --> 8589934191
• 8589934063 --> 8589931503
• 8313110527 --> 8321433087
• 8313110527 --> 8315207679
• 8313110527 --> 8271167487
• 8589885439 --> 8589917943
• 8589885439 --> 8451506175
• 8589885439 --> 8589721599
• 8589541375 --> 8589671391
• 8589541375 --> 8036024319
• 8589541375 --> 8589574143

The "transitions" for each depth are stored in the cell-array P.

After a few iterations, the number of possible states increases (more than?) exponentially. But at the same time, the number of duplicated states increases as well. This is, because there are different move sequences which result in the same game state. Hence, many paths also converge after a few iterations.

The number of new game states increases from 1 -> 4 -> 12 -> 60 -> 400 (296 of which unique) -> 2228 (1338) -> 11360 (5648) -> 51952 (21842) ....

After 4 moves, already over one quarter of the possible moves result in duplicate patterns, and the proportion of duplicate game states increases. After 7 moves, already more than half of the moves result in duplicate game states. All "transitions" are stored for backtracing, but only the unique game states are further propagated.

When limiting the "width" of the search window, the (unique) game states that had the least duplicates are pruned. This is a heuristic, as pruning the game states with the most duplicates leaves the search with a limited "width"" without a result.

The exhaustive search (the size of the corresponding P.dat is approximately 22GB) results in the following number of new moves after each step:

But the number of new unique game states at each depth is much less:

Interestingly, the search the the limited "width" finds the same final game states as the exaustive search:

• 0000065536
• 0000008192
• 0000524288
• 0000065536
• 0000065536
• 0000000002
• 2147483648
• 0000065536

We are only interested in the ones that end with one token in the center num2field(0000065536):

 0   0  -1  -1  -1   0   0
 0   0  -1  -1  -1   0   0
-1  -1  -1  -1  -1  -1  -1
-1  -1  -1   1  -1  -1  -1
-1  -1  -1  -1  -1  -1  -1
 0   0  -1  -1  -1   0   0
 0   0  -1  -1  -1   0   0

Backtracing from there can provide all intermediate game states. Like for the forward-direction, there are many many possible paths. By default, the script generates 1000 examples, by randomly selecting a move at each depth.

Some examples are shown in the teaser gif-animation. 1000 random example backtraces generated from the exhaustive search can be found in the subfolder solutions.