Multi-way system analysis of puzzles​
​by Amritesh Anand

Abstract

This project aims to explore one-player board games and sequential move puzzles. The first concern of this project is to analyze the complexity and solvability of the board game. Then, the next step involves the game graph and possible multiway graph for its solution and analysis. Peg solitaire attracted various famous mathematicians, from Leibniz to John Conway. So, this project progressed in the same direction.

Peg Solitaire

Introduction

It is a single-player board game that involves moving the pegs on a board with holes. The standard version consists of 33-holes, and an initial configuration has every hole except the center one filled with pegs. One can make a peg jump orthogonally from a filled position to an empty hole two positions away, and the middle one got removed. The goal is to reach the board configuration that has a single peg at the center position.
Now, let’s play one move and see what are the possible board configurations:

1
2
3
4
6
7
8
9
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
5
10
,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
15
16
,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
20
21
22
23
24
25
26
27
28
29
30
31
32
33
18
19
,
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
25
26
27
28
30
31
32
33
24
29


Game Graph

Its graphical representation is below, vertices are labeled with number of open positions.
Let’s traverse it to depth 3 :
One thing worth noting is that the graph is symmetric, and there is no board configuration till here, which can be achieved by multiway. Let’s go one level further :
Now it is evident that above graph contains many such vertices. What about going to depth 6 ?
Above graph has 7359 vertices and 14064 edges and each vertex represents unique board configuration. What about finding all solutions i.e going to depth 32? What about time taken to finish this? Don’t worry let’s look at the amount of time taken to finish up to depth 10 :
"33 Hole Peg Solitaire"
"Power Law"
"Exponential"
"Linear"
So, going to depth 32 will take
4.6164×
14
10
s
i.e
1.46385×
7
10
yr
. Not so random fact : age of our universe is
1.38×
10
10
yr
. So, let’s try analyzing other initial configurations.

Multi-way systems

According to Wolfram Alpha, “A multiway system is a kind of substitution system in which multiple states are permitted at any stage. This accommodates rule systems in which there is more than one possible way to perform an update.” Here different configurations are presented as a multi-way system and rules for state transitions are the rules of the game. (Of course!) So, for each configuration we are interested to know about the following states in this system:
1. Target Solution: board configuration which has a single peg and that must be at the central position (17 on the board)
2. Other Solutions: board configuration which has a single peg but not at the central position
3. Stalemate: board configurations that do not contain a single peg and further no possible moves are possible (stuck!)
4. Connected InComponent: board configurations which can lead to the solution
Branchial Graph
Graph representing the common ancestry of states in the multiway system. Each node represents a state of the system, and two nodes are joined if they are obtained on different branches of evolution from the same state.

Cross Configuration

​

Plus Configuration

​

Fireplace Configuration

​
​

Concluding remarks

◼
  • As there are 33 holes, there are 2^33 possible board configurations. We tried plotting the game graph starting from depth one and found how the number of vertices grown exponentially. At depth 6, the graph has 7359 vertices and 14064 edges. We analyzed the amount of time taken by the program, which finds all the directed edges for a graph to a particular depth, and estimated the time to come up with the whole game graph(i.e depth 32) to 1.46385*10^7 years.
    • ◼
  • The program can be made more efficient by the different implementations to reduce the time. Although it will not be of much use as implementing HashSet instead of List reduced time but in that saved time we are only able to go one more level deep (at depth 7). One approach to reducing time is to consider symmetry and draw different types of graphs. Its scope is open for the future.
    • ◼
  • Multiway systems for some configurations like the cross, plus, fireplace, diamond (not complete) are considered, and their game graph and the branchial graphs are obtained. One finding of the branchial graphs is that the solutions (target and other solutions) appeared as one component.
    • ◼
  • Casual graph can be implemented by defining the events as initial board position, corresponding moves and final board position, and then finding edges for overlap of events. So, it can be able to show is how taking different step causes no solution or solution. Further, there is scope for analyzing their branchial and casual graphs.
    • ​

    Keywords

    ◼
  • Peg Solitaire
    • ◼
  • Multiway System
    • ◼
  • Branchial Graph
    • ◼
  • Game Graph

    • Acknowledgment

    Mentor: Robert Nachbar
    I am incredibly grateful to my mentor for giving important advice and shaping my project and code. He is always available to meet and talk with me whenever I encounter difficultness during these weeks. This notebook would not have been possible without his generous help.
    I also wish to thank Stephen Wolfram for introducing this exciting topic and providing intuition about multiway systems.
    I must also thank Jonathan Gorard for providing knowledge about the branchial graph and all TA’s, especially Yorick Zeschke who helped me due course of this project.

    References

    ◼
  • Winning Ways for Your Mathematical Plays, Volume 4, by Elwyn R. Berlekamp (Author), John H. Conway (Author), Richard K. Guy (Author)
    • ◼
  • https://www.sciencedirect.com/science/article/abs/pii/S0305054805000195
    • ◼
  • https://www.wolframphysics.org/technical-introduction/the-updating-process-for-string-substitution-systems/the-concept-of-branchial-graphs/