Perplex City and Magic Squares

I vaguely remember hearing about Perplex City when it was first launched, but I was too caught up in just about everything else to take too much notice. I do remember thinking that a worldwide puzzle/scavenger hunt game with an online component sounded right up my alley, but I was disappointed that the “crossover into real-life” events were centered in a country I had never set foot in.

A number of times since then, I’ve been reminded of the game’s existence, most recently when I heard that Perplex City would be having its first official U.S. event right here in San Francisco…on a day when I already had obligations. In spite of my inability to attend the event, there’s been a resurgence in my interest, and last Friday while in Berkeley for a concert I picked up a few packs of “PC” cards from Games of Berkeley.

Whoo boy, the good times are a-startin’. I love myself a good mental workout, and the Perplex City cards provide just that in diverse forms and at varying intensity. From pattern-matching to pop-culture knowledge, logic puzzles, physics problems, political trivia all abound.

Probably my favorite aspect of Perplex City problem-solving so far is scripting solutions to some of the more complicated puzzles. When I was working on a solution for card #098 ‘Magic Square’, I came up with a script which can be used to solve any 4 by 4 magic square, where the rows, columns, and diagonals all add to the same number.

My first attempt was far less than ideal: it randomly arranged the 16 numbers and then tested to see if everything added up properly (i.e. bogosort). When I let it run for ten minutes at a time, it would run through about 12-13 million combinations and not come up with a single solution.

My second attempt used iteration to go through possibilites in a fixed order and guaranteed me a solution eventually…within the next 56 years (seriously, I calculated), if I let the script run constantly, it would check every possible arrangement of numbers for ‘magic squareness’.

My third attempt is the one I finally found success with. Essentially, it’s a modified version of the second script where I run validity tests incrementally instead of all at once after a square is constructed. The spaces within a square are filled in a spiral pattern and rows, columns, and diagonals are tested the moment they’re testable, which results in maximum efficiency.

Where the first script would have required hundreds or possibly thousands of years, and the second script nearly a lifetime, my third script only took about 23 minutes and 35 seconds to find all 924 possible solutions for a 4×4 magic square.

As it turns out, there are 54 unique solutions to the Perplex City Magic Square card.