AoM Ascension Riddle
in Ascension MMORPG (an Age of Mythology mod)
In this article, I'll show a general solution for the monument puzzle created by Zenophobia found on floors 5 to 9 using vector math.
Breaking down the - at first glance - confusing riddle into basic connections and formulas, which can be solved with low effort computation.
no guarantee for mathematical correctness in writing and proving
Last modified: 07/23/2024 10:32 AM
Table of Contents
-
Riddle Description
-
Mathematical Model
-
Solution Algorithm
-
Interactive Solution
Riddle Description
Given a series of monuments which are arranged in a circle, each one facing in one of four possible directions.
A monument can be connected to one or more other monuments.
The player can rotate a single monument clockwise by one step but connected monuments will rotate as well.
The goal of the riddle is, that each monument is facing the middle.
The riddle on the last floor is a special form as the monuments are not arranged in a circle but in a grid.
Additionally, there are two types of monuments where one type has to face north and the other has to face south.
Mathematical Model
To calculate a general solution, the riddle has to be modelled using mathematical concepts. In here we can describe three different types:
- The rotation of each monument
- The connections between monuments
- An action we can perform
Given a riddle of n monuments, each monument can have 4 different rotations. Therefore, we define a vector s containing n elements
holding an integer of ring mod 4 (s ∈ ℕ4n).
A 0-value would indicate a correct rotation, any positive number the rotations performed clock-wise
and a negative value rotations performed counter clock-wise related to the correct rotation.
All rotations combined in one single vector describe the changeable state of the riddle.
Next we have to specify how each monument is connected to each other. Therefore, we define a n x n adjacent matrix M,
where the value in the i-th column and j-th row describe the connection, 1 for connected and 0 if no connection is present.
The last thing we need to create a model for is the actions we can perform in the riddle.
Since we can rotate each monument one-by-one, we will have n different actions.
An action affects the monument we are attacking plus any connected monuments.
As the matrix already describes this behavior, we can simply take the i-th column of the matrix if we want to attack the monument indexed by i.
Mathematically, we define our actions as vectors of size n again, for the first monument it holds an 1 as first element and an 0 for any other elements.
Generally speaking, attacking monument i will hold an 1 at index i inside the vector.
Since we might also affect other monuments, we multiply the matrix with the given action vector to get our final vector vi.
Now we got everything we need for the calculation. The mathematical model for the screenshot above would look like this:
$$
s_{initial} = \begin{bmatrix}0 \\1 \\2 \\3 \\2 \\0 \\3 \\1 \\1\end{bmatrix}
\hspace{5px}\text{and}\hspace{5px}
M = \begin{bmatrix}1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1\end{bmatrix}
$$
Solution Algorithm
Now we only need find a way to get to our final state. In the final state, each monument is pointing to the middle, which means we simply have a zero-vector:
$$ s_{final} = \begin{bmatrix}0 \\0 \\0 \\0 \\0 \\0 \\0 \\0 \\0\end{bmatrix} $$
And how can we achieve this state? Well, we need to apply \(k_i\) operations on each monument \(i\). This leads to the following equation:
$$ s_{initial} + \sum_{i=0}^{n-1} k_{i} * v_{i} = s_{final} $$
So all we need is finding suitable values for k. Bringing the initial state on the other site by subtracting it on both sides we can transform the
equation into a matrix notation:
$$
k_{0} * \begin{bmatrix}1 \\0 \\0 \\1 \\0 \\0 \\0 \\0 \\1\end{bmatrix}+k_{1} * \begin{bmatrix}0 \\1 \\0 \\0 \\1 \\0 \\0 \\1 \\0\end{bmatrix}+k_{2} * \begin{bmatrix}0 \\0 \\1 \\0 \\1 \\0 \\0 \\1 \\0\end{bmatrix}+k_{3} * \begin{bmatrix}1 \\0 \\0 \\1 \\1 \\0 \\0 \\0 \\0\end{bmatrix}+k_{4} * \begin{bmatrix}0 \\1 \\1 \\1 \\1 \\0 \\0 \\0 \\0\end{bmatrix}+k_{5} * \begin{bmatrix}0 \\0 \\0 \\0 \\0 \\1 \\1 \\0 \\0\end{bmatrix}+k_{6} * \begin{bmatrix}0 \\0 \\0 \\0 \\0 \\1 \\1 \\0 \\1\end{bmatrix}+k_{7} * \begin{bmatrix}0 \\1 \\1 \\0 \\0 \\0 \\0 \\1 \\0\end{bmatrix}+k_{8} * \begin{bmatrix}1 \\0 \\0 \\0 \\0 \\0 \\1 \\0 \\1\end{bmatrix}=\begin{bmatrix}0 \\0 \\0 \\0 \\0 \\0 \\0 \\0 \\0\end{bmatrix}
\hspace{10px}\longrightarrow\hspace{10px}
\begin{array}{ccccccccc|c}1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & -1 \\0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & -2 \\1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & -3 \\0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & -2 \\0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & -3 \\0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & -1 \\1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & -1\end{array}
$$
Now this equation system is easily solvable with the
gaussian elimination but has to be modified a bit,
since we are working on a finite ring (\(\mathbb{Z}_{4}\)). Firstly, we are not allowed to swap rows inside the matrix, because we would lose the relation between
the monument and the number of rotations needed for them. Secondly, we cannot use division since we could get fractions which are not part of our finite ring. Instead,
we have to work with modular multiplicative inverse elements.
$$
\begin{bmatrix}-12 \\-5 \\-6 \\15 \\-6 \\-14 \\14 \\10 \\-3\end{bmatrix}
ext{mod}\hspace{5px}4 =
\begin{bmatrix}0 \\3 \\2 \\3 \\2 \\2 \\2 \\2 \\1\end{bmatrix}
$$
Interpreting this result, we have to attack the second monument 3 times, the third monument twice and so on.
The riddle is solved. \(_\Box\)
Interactive Solution