In "Adventures in Groups Theory", David Joyner points to a post by D. Rusin. In it, one Carsten Haese lays out the solution to a similar game that can be applied to Poggle. I will attempt to reproduce it in this post.
Short form: convert the game to linear algebraic form and solve. Not-so short form: stock up on asprin.
Think of Poggle as a state machine with; a internal state (here, the buttons that are light), an input alphabet (the buttons), an output alphabet (the lights), an internal trasition table (the new internal state, given a specified internal state and the input), and an output table (given an internal state and an input, the output). As the output, input and internal state can be folded into one set and the tables can be considered as one, there are only two items that need to be looked at.
The state can be represented by a one-dimensional vector that is n-squared elements long. Think of this vector representing the Poggle board's display layed out row by row (from top to bottom).
Now to build the transition table. The size of the table will be n-squared by n-squared elements. The building blocks cosist of;
the Identity Matrix (size n-by-n),
the Zero Matrix (size n-by-n), and
| B | = |
| ||||||||||||||||||||||||||||||
The construction of the B matrix is placing 1's in the main diagonal of the n-by-n matrix and in the diagonals above and below it. 0's are placed every where else.
The transition matrix is formed
| A | = |
| ||||||||||||||||||||||||||||||
For instance the 3-by-3 Poggle board's transition matrix is;
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
For Poggle the solution can be foudn with the linear equation;
(A x = s0) mod y.
where s0 is the starting vector (a 1 dimensional vector containing n-squared 1's for Poggle), and x is the vector containing the buttons to input. The modulus y is simply the total number of colours that the program cycles through.
Using {a,b,c,d,e,f,g,h,i} to denote the solution vector, the 3-by-3 Pobble board can be solved with the solution of;
a + b + d = 1 mod y,
a + b + c + e = 1 mod y,
b + c + f = 1 mod y,
a + d + e + g = 1 mod y,
b + d + e + f + h = 1 mod y,
c + e + f + i = 1 mod y,
d + g + h = 1 mod y,
e + g + h + i = 1 mod y,
f + h + i = 1 mod y.
For y=2 it is easy to see that {1,0,1,0,1,0,1,0,1} is the solution.
No comments:
Post a Comment