08.13.06
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.
Oliver said,
October 31, 2006 at 10:18 pm
Hi, I’m a software engineer, and I find your approach interesting. I wrote a small code as an exercise to solve N x N squares on my spare time. My results for the 4 x 4 were different. I got 7040 solutions in 466 seconds. What i did was I iterated over all the possible permutations. I truncated the trees that will never arrive a solution checking only the partial array as necessary. I believe that you have ommitted a lot of the possible solutions. :)
Matt said,
March 6, 2008 at 8:03 pm
Hey I am also a software engineer and I noticed that you are missing quiet a few answers one being the magic square of
7 2 11 14
12 13 8 1
6 3 10 15
9 16 5 4
Else very interesting and good attempt
Marcel said,
March 12, 2008 at 8:20 am
Hi,
nice that you are also interested in magic squares and a nice attempt to find solutions.
I see that your program finds 924 solutions for a 4×4 magic square. However, in reality there are lots more.
But there are 880 unique solutions (a unique solution cannot be obtained by rotating and/or mirroring another solution).
I wrote a program in Fortran which can find all solutions for magic squares of any length.
It can be run under DOS or Windows.
You can download it freely at download.com (the name is magic square generator 1.0).
For 4×4 it will find all 880 solutions in about 5 minutes. My approach is comparable with yours by incrementing numbers and testing rows, columns and rows as soon as possible.
However the order I incremented numbers was different (e.g. for 4×4, for other sizes similar):
a b c d
e h i j
f k m n
g l o p
I hope you enjoy the program.