Cross Sums



A little while ago, I realized something was missing in my life. There was a hole in my heart that was crying out to be filled. None of the things I tried to fill it with (drugs, alcohol, sex, family, religion...) seemed to help. Then one day, I realized what I was missing: Cross Sums.



For those of you (if any exist who read this blog) who are unfamiliar with Cross Sums, they are essentially Cross Word puzzles, but filled with numbers and the clues represent the sums of the numbers that fill in the squares in the row or column. They are in Dell puzzle magazines, and were a staple of my bathroom time until I moved out of the house and went to college. In college, mom would xerox (verbing weirds language) them and send them to me, but as there were no tables in the stalls in Marian Hall, I tended not to do them. But recently, I've found myself longing for their logical intrigue, especially since I have long, boring periods of downtime at work.



Being a cheap b------, I decided I didn't actually want to pay money for a Dell puzzle magazine subscription, and Dell refused my offers to sell them my wife for a life time subscription, so I remained Cross Sum-less. Then one day, I had a thought, as if a bolt of lightning struck my brain. Yeah, they tend to hurt. "Hey, I'm a CS major," I thought. "I could just write a computer algorithm to randomly generate a Cross Sum." An intriguing idea, my split personality agreed. So thus the work began. I rolled up my sleeves and dove into Visual Basic head first, after the initial struggles of coming up with how to generate a grid symmetrical to a point and guarantee that no runs are shorter than 2 or longer than 9, then getting my head round the recursive algorithm I was using to generate the random numbers to populate the grid, I had myself a bonifide, electrifide, genuine Cross Sum. What's it called? Cross Sum! One more time! Cross Sum. (< /simpsons >)



So, with great anticipation, I jumped into the puzzle and began solving it, only to discover that Dell puzzle magazine doesn't just throw together Cross Sums. Apparently, it requires actual work. The problem I immediately encountered with my random-number Cross Sum was that it was, well, random. There was no unique solution. You could pretty much put whatever numbers you wanted into the grid and get it to work out in the end. This somehow diminished the fun and logical challenge. Disappointed, I put down the Cross Sum and was ready to give up. This made the kittens cry.



Then while discussing the problem with Dave, he suggested an idea that might help make it possible. When I randomly generated a number for the grid, I made several checks on that number to make sure it would validly fit in the grid. How about if one of the checks was a unique solution? Before it could accept a particular placement of numbers in the grid, it would have to first check that the placement was unique. This shouldn't be hard at all! All I'd have to do is check to see if there are two solutions and, if so, change the numbers somehow to get rid of one of them. Solving the Cross Sum in an algorithm shouldn't be hard at all. In fact, it would be a very similar algorithm to generating. So with a renewed sense of eagerness, I dove back into VB, and began writing the algorithm to solve the Cross Sum I'd just generated to see if there are different solutions.



That's where the real problem comes. Technically this is entirely possible to do. Basically, to find out if there's only one solution, I have to test all possible combinations of the 9 digits in each square, do various tests to weed out the invalid digits, and make sure they add up properly. Put this in another recursive function and voila, I have my solving algorithm. The problem: each square has 9 possible digits, each of which I have to test for. The default grid size is 20x20 (400 squares). So that's 9^400 possible combinations, or 4.977 x 10^381. Assuming one clock cycle per digit, (when in reality it takes several hundred), it would take a 3.0 Ghz machine about 5.261 x 10^364 years to iterate through all possible combinations. Not good.



There are ways to simplify it. I can immediately rule out some digits (a 9 can't go in a 2-digit combination that adds up to 3, for example), so I can reduce the possibilities some there. Also, I'm not really solving for 400 squares. Minus the border and the internal blocks, it's really only about 250-300 squares. Assuming an average of 4.5 possible digits for each square, this bring down the number of combinations to no more than 2.010 x 10^163, which is solvable in a mere 6.373 x 10^155 years. Doing a little better. If I lower the grid size to 10x10, and assume about 30 internal blocks, for a total of around 50 squares, I have a paltry 4.577 x 10^32, solvable in only 14.52 septillion years (14.52 x 10^24). Just the blink of an eye.



Essentially, the problem is the number of combinations is an exponential function of the grid size, so the solving algorithm runs in exponential time, based on the size of the grid (or O(n) = (9-c1)^(n-c2) where c1 represents the average number of unusable digits, c2 is the number of blocks, and n is the size of the grid, for those of you interested in Big O notation). Is there a way to simplify it? Well, no one knows. Essentially, it runs in what is referred to as "Non-deterministic Polynomial Time", and as such this algorithm is a member of the set NP (the set of all algorithms solvable in Non-deterministic Polynomial Time). It's called this because each iteration of the loop runs in Polynomial time (which is faster), so if we arbitrarily choose (non-determinism) one iteration of the loop, we can run that in Polynomial time. But the larger the grid, the more (exponentially) iterations of the loop.



By contrast, an algorithm that increases more steadily as the independant variable increases is said to run in "Polynomial time". In our case, if we had a Polynomial time algorithm, the run time would be something more like O(n) = c*n^x. As n increases, the computational time increases at a more manageable rate. The set of these desirable, fast algorithms - those that can be solved in Polynomial time - is referred to as P. So in essence, to get a suitably quick Cross Sum generator with guaranteed unique solutions, I have to solve the problem of P=NP, one of the great unsolved problems in mathematics: is the set of algorithms that can be solved in Non-deterministic Polynomial time equal to the set of algorithms that can be solved in Polynomial time. Basically, can you convert an exponential-time algorithm into a faster polynomial-time algorithm? Most mathematicians believe the answer is no, but no one has ever been able to prove this definitely.



So now, the stakes for the Cross Sums generator are much higher. If I can write a quick program, not only do I fill a whole in my heart, but I also get the Nobel prize in Mathematics, millions of dollars, and a place in history as a great mathematician. Oh, and hot babes. All brilliant mathematicians had loads of hot babes.