Thursday, July 4, 2013

Solving Assassin's Creed's picture sliding puzzles with systems of linear equations

As anyone who is familiar with the Assassin's Creed series will know, the creators like to feature logic puzzles and riddles as an important part of the story telling.

One such puzzle in particular involves a circular image that has been broken down into a center node and 4 rotatable rings. The player is tasked with configuring the rings such that they form the correct picture in the correct orientation. 

An example might look like this:

Where, for clarity, the desired result looks like this:

Here's the catch: You can never just move one slice at a time. Every choice of possible move you can make (in this puzzle) moves two different rows. 

First, some terminology:

Let's label the rotatable slices, from inward to outward (NOT counting the static center circular piece that does not move) as:

\[ A, B, C, D \]

In this particular puzzle, your choices include:

A and B:

B and D:

C and D:

or A and D:

This puzzle, for me, was where it got unproductive and eventually impossible to just guess around by feel and eventually solve the puzzle by trial and error.

So, I set out to determine a general algorithm that could solve any of these puzzles. How do we do that? Turns out it's as simple as a system of linear equations!

First, we need some more terminology. We need to establish a numerical value for these rotatable slices. 

Because the center node does not move, each slice has a unique "correct" position. We will call that "0". The orientations of the slices will now be measured in terms of their offset from their correct position. 

It should also be noted that the rings rotate 10 times before arriving at the same spot. So in a sense, this all occurs modulo 10.

By quick trial and error, it is trivial to determine the initial conditions of the puzzle you are given. For this particular puzzle, it can be seen that:

\[ A_0 = -1 \]

\[ B_0 = 5 \]

\[ C_0 = 0 \]

\[ D_0 = 2 \]

In other words, A is one to the left of its correct position, B is opposite its correct position, C is already correct, and D is two to the right of its correct position.

In the spirit of even more terminology, we need to name the moves we can perform.

Move \(0\) moves slice \(A\) and \(B\).
Move \(1\) moves slice \(B\) and \(D\).
Move \(2\) moves slice \(C\) and \(D\).
Move \(3\) moves slice \(A\) and \(D\).

Now for the kicker - introduce the following notion:

Let \(m_0\) represent the number of times we apply move \(0\)
Let \(m_1\) represent the number of times we apply move \(1\)
Let \(m_2\) represent the number of times we apply move \(2\)
Let \(m_3\) represent the number of times we apply move \(3\)

With this framework, we can express the position of any particular ring in terms of the variables \(m_0, m_1, m_2, m_3\)

For example

\[ A = -1 + m_0 + m_3 \]

This comes from the fact that \(A\) starts at \(-1\), and an application of move \(0\) or \(3\) will both move ring \(A\)


\[ B = 5 + m_0 + m_1 \]

\[ C = 0 + m_2 \]

\[ D = 2 + m_1 + m_2 + m_3 \]

Since the goal is to end up with all the rings at 0, this means we are looking to solve the system of equations formed by setting all the equations above equal to 0:

\[ m_0 + m_3 = 1 \]

\[ m_0 + m_1 = -5 \]

\[ m_2 = 0 \]

\[ m_1 + m_2 + m_3 = -2 \]

This can be solved simply with a calculator or matrix methods. The result yeilds:

\[ m_0 = -1\]

\[ m_1 = -4 \]

\[ m_2 = 0 \]

\[ m_3 = 2 \]

How do we interpret this?

Well, those variables represent the number of times we should apply each of their corresponding moves. A negative number, of course, just means to apply that move to the left instead of the right.

Sure enough, if we perform move \(0\) once to the left, move \(1\) 4 times to the left, move \(2\) zero times, and move \(3\) twice to the right,

we end up with the correct picture!

This method will work no matter what initial condition the puzzle is in or the number of available moves or rings.

1 comment:

  1. Cute method, but seems like overkill here. Assuming n rings and n moves (each move is a pair of rings), consider the graph whose vertices are rings, and whose edges are moves. Either this graph has a pendant vertex (degree 1) or consists of one or more disjoint cycles. In the example above, C is a pendant vertex, since only one move affects it. As long as there are pendant vertices, take the (unique) moves to align them -- then delete the vertex and move, and we now have (n-1) vertices and (n-1) edges. If the graph consists of cycles, treat each cycle separately. A cycle of even length is linearly dependent, in your notation, so we may delete any edge and now we have pendant vertices again. To handle a cycle of odd length, first make all the displacements even by choosing arbitrary moves. [if there are an odd number of odd displacements, the puzzle can't be solved]. Then, make each move of the cycle alternately + and -; this will turn a single wheel by 2 while leaving the others unchanged. In the example above, {A,B,D} form a cycle. In the first move, turn AB so that all three are even. Then +AB-BD+DA turns A by 2, etc.