Solving the “Rotation” puzzle in stages

Introduction

A few months ago (in June last year), I wrote a simple puzzle named “Rotation”  (play here) that involves rearranging a grid of jumbled-up numbers in order by rotating groups of numbers about.

Jumbled-up grid

The player clicks on the cyan colored buttons in order to rotate the group of numbers immediately adjacent to it clockwise. In the above example, rotation  rotates clockwise such that is now where was, and so on. The goal of the game is to rotate the numbers about until all the numbers on the grid are eventually in the correct order:

Ordered grid

In this article, we develop an AI that solves the puzzle using a sequence of 8 stages. The AI places the numbers into their correct positions one by one at each stage. The possible number of game states reduces after each stage until there is only one possible game state left, and the puzzle is solved.

The stages, in sequence order

As mentioned earlier, the strategy we will be employing is to move the numbers into their correct positions one by one, without affecting the positions of the numbers corrected in the preceding stages. The top row is completed first, followed by the bottom row, and finally the middle row. The exact order of correcting the numbers is

Note that despite having 9 numbers, there are only 8 stages instead of 9 stages. This is because placing the preceding 8 numbers in their correct position leaves only one possible position for the last number – which is its own intended position.

The decision matrix

At each stage, the corresponding number is moved to its correct position using a sequence of rotations depending on the current position of . We define the decision matrix with entries such that if the number is currently at row and column , the rotation(s) executed by the AI will be . This will be repeated until the number is at its intended position.

We will use the first stage as an example. The first stage moves the number to the top left corner. The corresponding decision matrix is given by

Suppose the number is currently at the bottom left corner (row , column ). Then, using the decision matrix, rotation will be executed, moving to the leftmost corner of the middle row. Since is still away from its correct position, the decision matrix will be applied again – rotation will consequently be executed, shifting to its correct position.

Note that , the identity element – this means that if the intended number is already at its intended position, then no rotation will be made and the AI will proceed immediately to the next stage, described by .

Having moved the intended number to its intended position, the AI moves on to the next stage. The stages are completed sequentially in this manner until the puzzle is eventually solved.

Exact decision matrices

The decision matrices used by the AI here at each of the stages is given exactly in order below. As the stages are to be executed sequentially, there are some positions at each stage where the intended number cannot be, as the correct numbers are already moved to these position in the preceding stages. These illegal positions are marked with the element in the decision matrices.

Note also that for better intuition, anticlockwise rotations are denoted by instead of . Of course, the rules of the game are such that only clockwise rotation are allowed. As such, when we encounter , we will execute it as .

Implementation and analysis

The AI described here is implemented alongside the game itself (link).

From the decision matrices, the maximum number of rotations needed at each step sum up to

clockwise rotations. That is, it takes at most 53 moves to complete the puzzle.

The number of cases considered by the AI at each stage sum up to

In contrast to the brute force method of coming up with a solution sequence for each of the possible puzzles, the small number of cases to be considered requires a lot less memory space. However, more moves are required because the game states can sometimes be solved by shorter rotation sequences, but these shorter sequences are not identified by the AI.

Conclusion

While it is possible to come up with faster strategies which consider more cases, the aim of this article is to allow the reader to have a general idea of how to solve “Rotation” – and similar puzzles – using the approach of breaking up a strategy into stages. As such, the strategy used in this article is simpler albeit slower, and the exploration of more complex strategies is left to the reader.

Advertisements