[E18 PUZZLE SPOILER] Brute force vs. the double magic square puzzle

[Sejiren]

Recently, I started a new playthrough and came across the wonderful puzzle in the Devon Corp. building requiring the Meteor ID. I took a good hard look at it and decided I didn't want to deal with that, so I asked myself: "Could it be possible to brute-force that?"

 

Just so you don't get your hopes up, the short answer is "no" and also this is not a guide to actually solve the puzzle. The long answer requires some math, so if you are not into that, this post is probably not for you.

 

To explain the situation, the puzzle I talk about is set on a 3x6 grid with 3 rows and 6 columns. Every digit from 1 to 9 is found exactly twice on the grid. The goal is to fit two 3x3 magic squares into the grid with each 3x3 square summing up to 15 in each row, column and the diagonals, with the second 3x3 not having any same number at the same position as the first one.

 

The setup looks like this (shout-out to Aboodie for uploading this screenshot in his Item Guide) :

 

 

If all 18 slots contained a different number, there would be 18! = 18 * 17 * .. * 1 = 6,402,373,705,728,000 possible states for the grid. Luckily, each digit from 1 to 9 is present twice, so any combination of digits may be flipped to still give the same state. That is 2^9 = 512 combinations of digits, thus the number of unique states is 18! divided by 2^9 = 12,504,636,144,000 (unless I'm not thinking straight here).

 

That is still a lot of states, too many to realistically check in a brute-force algorithm. But maybe, there are enough solutions to find to still justify a brute-force method. Unfortunately, as is explained here, there is a whopping 8 solutions per magic square, which is in fact one solution rotated 4 times by 90° and mirrored for every rotation. So even if it was possible after finding 1 of 8 solutions for one square to get 1 of 7 remaining solutions for the other square (remember, no duplicate positions), and the other way around for solving the other square first, we would be stuck with 7 * 8 = 56 solutions in total. Or to put it differently, 1 in every 18! / 2^9 / (7*8) = 223,297,074,000 states is a solution to the puzzle.

 

That still does not bode well, but math never stopped me from wasting my time, so I put it to the test:

 

I started a new Java-project and implemented data-structures for the different states of the grid, as well as for the sequences of moves that led to that state in form of a tuple (state, move sequence), since I want to know which moves to take to solve the puzzle in as little steps as possible. I implemented methods to rotate the states, rows left or right, columns up or down. I slapped a graphical user interface onto it to enter the initial state manually, a large text field to display the order of the moves, and a button to start the mayhem.

 

 

 

The actual algorithm takes the initial state, puts it in a set collecting all visited states, a assigns an empty sequence of moves to that state. The sequence object is put into working queue. A sequence that is removed from the queue has its attached state rotated in every possible way, appends the move sequence with that rotation, and checks if the newly generated state is a solution. If yes, the solution is displayed, otherwise, if the new state was not yet visited, the new sequence goes into the working queue to be processed once all moves for the current state were tested.

 

So, with 6 columns and 2 moves each, plus 3 rows and 2 moves each, that's at most 18 possible moves that go into the working set for every 1 move going out (at most 17 after the first state actually, moving back to the previous state by using the opposite rotation guaranteed leads to a state already visited).

 

To remind you, the algorithm needs to go through 223,297,074,000 states on average to find one solution. After about 900,000 states, it breaks down. 

 

Conclusion: Maybe it is possible to make some optimizations, I am using a fairly naive algorithm to to solve the puzzle. Maybe using a different programming language would help, the Java garbage collector is pretty much killing my CPU cleaning up all those finished sequences from the working queue. But the queue still contains around 15,000,000 sequences to rotate. With 900,000 states checked, I got into checking 5 moves in a row. But I enjoyed doing that little experiment, and if someone finds some errors with my math, please correct me if you bother to actually read this to the end. 

 

The ordeal had a happy end, though. After spending two afternoons to build a brute-force algorithm for the puzzle, I solved it in like 20 minutes with some good old thinking.

 

[Marcello]

Now this is the kind of thing I like to read! I will point you to this post I made in the devblog before E18 released

 

 

Which was essentially the result of Ame having developed this puzzle and asking me if it could be solved. I used Ruby and wrote a very basic programme which made moves randomly and checked if I had a winning combination.

[Sejiren]

Thanks for the reply, that's really interesting. I guess with random moves, eventually I would have found a solution without running into space problems, albeit one that is completely impossible to actually do in game before the end of time

 

I did think about proving the solvability of the game, but it's been a while since I did something like that. I know you can easily enough get to 5 correct columns by simple back-and-forth switching, and getting the last column in the right order (if not already so) can be done by switching out one of the tiles with an equal tile of the other square (happened in my own solution).