PuzzleTwist is now available!

My latest creation is now up on the iTunes App Store. It's called PuzzleTwist, and it's a puzzle game where you unscramble a picture by rotating the pieces.  As each piece is rotated into place, others will rotate as well - some in the same direction, some in the opposite direction. The key to solving the puzzle is to figure out what order to move the pieces in.

One unique feature is that the rules for each puzzle are different - some are simple, some are more complex. A few are so difficult that I can't solve them without looking at the solution.

Once you've solved a puzzle, you can save the resulting picture in the Photo Library on your iPhone, and then use it as the wallpaper image for the phone, or assign it to one of your contacts.

PuzzleTwist also keeps track of the best reported scores, so you can compare your scores versus the rest of the world.

If you're a puzzle fan, you should check it out. Here's the iTunes store link.

On a side note, this application was approved much faster than the previous applications I submitted. Perhaps the App Store review team is coming out from under their backlog.

A math problem

Okay, so here's an example of where dropping out of math classes after Differential Equations is coming back to bite me a bit. I'm working on a kind of puzzle, mostly for fun, but possibly to incorporate into a future software product.

At its most basic, the solution process for the puzzle turns out to be solving a system of simultaneous equations. Which is something I learned how to do way back in High School, and for linear equations, I can even find off-the-shelf algorithms and libraries for doing so.

The catch, of course, is that these aren't linear equations. They use modular arithmetic, which is something I understand at a basic level, like anybody who programs for a living probably does, but I don't know where to even start breaking this down to solve a non-trivial version, and Google isn't helping me.

Let's start with a simple linear example:
5x + 7y + 4 = 0
4x + 3y + 1 = 0

Use whatever method you like, and you get:
x = 0.3846
y = -0.846

Piece of cake. Now, what if the equation looks like this?
5x + 7y + 4 = 0 (modulo 16)
4x + 3y + 1 = 0 (modulo 16)

If we want to find a few integer solutions for x and y, how do we find them? I could write a program to just guess every integer between 1 and 1,000,000 for each of the coefficients, and that'd find me a solution, but it doesn't scale well if I have a large number of variables. In the example equations given, there are rather a lot of solutions ([9,9],[9,25],[25,25]...), but I suspect that some other (carefully chosen?) sets of coefficients would have a much smaller set of solutions. Actually, that's kind of the point of the whole exercise.

Anyone out there got some hints for me?
Googling "simultaneous modular equations" got me:
http://en.wikibooks.org/wiki/Discrete_mathematics/Modular_arithmetic#Simultaneous_equations
and
http://www.nada.kth.se/~johanh/rsalowexponent.ps
,both of which are interesting, but not quite what I'm looking for.

For the case where the modulus is 2, addition is equivalent to XOR, and so logic minimization techniques from EE can be used, but it's not clear to me how to move those up to work in a higher modulus.