Attempting to “solve” the peg game...
Solution.
I started by taking my existing JavaScript code and translating into Python. Once I had the implementation ported over, I started trying to enumerate the possible game states. Given that my original game state in JavaScript is essentially an array of boolean values, I used a binary representation of the game board to turn my state into a single integer in the range from \(0\) to \(2^{33}\text{.}\) Under this representation, my intitial state corresponded with \(8589869055\) and terminal state corresponded with \(65536\text{.}\) A hypothetical solution would correspond to a sequence of 32 game states beginning and ending with the specified values, such that each step is a valid move.
There’s a slight problem with this approach, namely that it would would essentially require me to work with a \(2^{33} \times 2^{33}\) adjacency matrix in order to model how these states are connected with each other. While I could step through and evalauate which states are accessible from every other state, it would take an extraordinary amount of time to do so.
This, in turn, got me thinking about the adjacency matrices of graphs that I was looking at last week. Like my game states, these too could be turned into integers by thinking of the matrix elements as the bits of a single number \(n\text{.}\) If you could also encode the size \(s\) of the matrix into an ordered pair \(\langle n, s \rangle\text{,}\) that would give you all the information you need to reconstruct the adjacency matrix. If you knew the graph is an endomap, the size wouldn’t even be necessary because the size of matrix would be uniquely determined by the number of bits in the “on” state — because this graph would necessarily have a one-to-one relation between dots and arrows.
That’s where I had an epiphany. My terminal state for the peg game isn’t just a board with one filled slot in the center, as my bitfield representation depicted, but rather that peg in the center needs to correspond with exactly one of the initial 32 pegs placed on the board. Since each peg can only move up 2, down 2, left 2, or right 2, they essentially forced into four distinct groups based on whether they are in “odd or even” “rows and columns”. I numbered these slot groups 0 through 3 as per the following arrangement:
020 131 0202020 1313131 0202020 131 020
This labeling makes it clear that only four of the original 32 pegs can ever end up the center slot. Furthermore, these same four pegs have a one-to-one correspondence with the four possible peices which are removed first because the opening move must move one of those same four to the center also. Pairing an opening move with a closing move would define a class of 4 possible solutions up to rotation and reflection.
Without loss of generality, we can assume the first move to put the board into the following state:
XXX XOX XXXOXXX XXXXXXX XXXXXXX XXX XXX
We also know that the peg that ends up in the center must be one of the original set of four first moves. If this last peg is one other than the first moved, that first peg will need to move out of the center slot at some point before a new peg can move in. That final peg can also not be removed by any move, but every other peg is removed by exactly one peg. The relationship between the pegs removed and the pegs moved is “onto” but not necessary “one-to-one”. Similarly, the slots in the corners of the game board have a special property: each of these corner pegs can’t be removed until after it’s moved.
All of these conditions could be used together to help narrow down the possible solution space. Each solution must correspond to a sequence of 31 “removals”, with every one of the 32 pegs except the terminal one having exactly one turn in which it is removed. If I think of the first move and the last move as being paired together, this essentially would give me a retraction. Similarly, there should be some kind of section on this map which identifies which peg moves in a given turn. We can “sort” the pegs based on ones which may move more than once, move at least once, or get removed without ever moving at all.
By looking at these points as a “sequence of removals”, I can effectively narrow down my search space to \(31!\) possible permutations. This is far less than the \(2^{33}!\) sequences of game states I was originally looking at, but still too many for practical purposes.
In an effort to explore this, I tried to see how well I could recreate the game state from a given sequence of removals. This turned out to be a little more difficult than I anticipated. There are various different board states which knowing which peice is removed in a given turn is not sufficient identify a unique move. It’s entirely possible that turns could arise in which a given peg could be jumped by two different pegs. You wouldn’t know which peg does the jumping by looking at the sequence leading up to that point, so this information would need to be encoded somehow by the removals after that turn.
I’m starting to think that the key to this lies in keeping track of the domains and codomains of each these “maps”. In the same way that thinking of a difference between “slot space” and “peg space” helped reduce my number of options, maybe I can somehow use a product of the “peg moved” and “peg removed” to help narrow my solutions further.
Before I wrap up for the week, I think I want to document some of the maps I’ve encountered with this problem so far. I’m thinking this will be useful reference to have as I start organizing a sequece of compositions that results in a “solution”. I put solution in quotes, because identifying the exact structure of that object seems to be a large part of the problem to begin with. So far, I’ve had to identify the following maps:
- A map from \(\mathbf{7} \times \mathbf{7} \longrightarrow \{\text{slot},\text{no-slot}\} \) identifying the 33 slots on the 7 by 7 board.
- A map from \(S_{33} \longrightarrow \mathbf{7} \times \mathbf{7}\) assigning each of the 33 slots with its respective row and column pair.
- A map from \(P_{32} \longrightarrow S_{33}\) assigning each of the 32 pegs with its initial slot.
- A map from \(P_{32} \longrightarrow \{\text{removed},\text{not-removed}\}\) that identifies which pegs are eventually removed in a given solution.
- A map from \(\mathbf{1} \longrightarrow P_{32}\) that identifies the last peg remaining on the board.
- A map from \(\mathbf{1} \longrightarrow P_{32}\) that identifies the first peg removed from the board.
- A map from \(P_{32} \longrightarrow P_{32}\) that pairs each point with the peg that removes it or itself if it’s the last peg.
- An isomorphism from \(P_{32} \leftrightarrows T_{32}\) that pairs each point with the number of the turn in which is removed from the board, with the last peg being being thought of as removed in the last turn.
- An map from \(T_{32} \longrightarrow P_{32}\) that maps each turn to the peg that moves in that turn.
- A map from \(P_{32} \longrightarrow \{\text{moves},\text{removed-without-moving}\}\) that sorts pegs into ones that move and ones that never move.
- A map from \(P_{32} \longrightarrow \{\text{must-move-before-removed},\text{removable-without-moving}\}\) that sorts pegs based on whether they can be removed before they are moved or not.
- A sequence of maps from \(P_{32} \longrightarrow P_{31} \longrightarrow ... \) representing the coimages of the pegs left on the board after each turn.
- A set of maps from \(P_{n} \longrightarrow S_{33}\) representing the state of the board with \(n\) pegs left.
- Several isomorphisms \(S_{33} \leftrightarrow S_{33}\) corresponding to rotations and reflections of the game board.
- Some map \(\mathbf{1} \rightarrow \mathbb{N}\) describing the number of potential solutions up to rigid transformation.
- A map \(T_{32} \longrightarrow P_{32} \times P_{32}\) that maps each of the turns to a \(\langle \text{moved}, \text{removed} \rangle\) pair.
While exploring, it seemed like one possible strategy might to work forward and backwards simultaneously by pairing up the turns from the beginning with turns from the end. I wonder if this might have some relation to the “graph negation” operation that I was looking at last week. I think if I can somehow combine this idea with the approach to Session 10 Exercise 4, I might be able to find a point where the forward and backward paths intersect.
