How to Make a Sudoku Puzzle
admin on Jul 26th 2008
A number of months back I found myself needing to board a plane to visit a sick family member. On my most unpleasant trip I noticed a few things. (not that the destination was unpleasant btw, just the trip part) One thing is just how many of the people at the airport are there because some loved one is dying. Sitting at my terminal waiting I noted the conversation of three different groups of people who were off to visit people in the hospital. Thats just the conversations that were within earshot. Another thing I noted is that I am far less worried about terrorists than I am about security guards, and abuse in general by the airlines. It was in preparation for this trip and the painful experieces to come that I stopped off and bought a sudoku puzzle book.
After the return trip this book became consigned to the restroom literature pile. I’ve spent the last few months looking across at this book setting on the magazine rack at least once every day. Another thing I’ve noticed is that all of my great inspiration seems to happen whilst I’m setting on the porcelain and out of reach of pen and paper. That same inspiration is often lost about the same time as the flush sound happens. I’ve had tons of great ideas in the bathroom, but I can’t remember any of them now. (Not sure why I can remember having them but can’t remember what they were?)
Anyhow it occurred to me that I was a bit curious about How a sudoku puzzle is made. So after a bit of research I thought I’d blog today about what I learned. Have you ever seen something that looks really complicated to make and then discovered that its lots easier than it seems. A couple of things that fit that category are the paper cup holders restaurants give away and soda pop bottles. The paper cup holders are made by a mesh screen with a vacuum attached to it bieng dipped in a vat of liquified paper. For soda bottles I knew they were blow moulded, but I couldn’t see how you could blow air into liquid plastic, and have it seal/take shape. They are actually injection moulded into hollow capsules and then the capsule is loaded into a mold where the air expands the chamber in the capsule to the size of the mold.
Making a sudoku puzzle is essentially the same idea. looking at those numbers and trying to figure out how anyone could make the puzzle seems overwhelming. If it sometimes takes you minutes/hours/days to figure out how to solve the puzzle how could someone else see the solution and make a puzzle using it? Are you ready for the answer? Ok I’ve dragged it out long enough.
They start with a solved grid. Then they remove a number and see if it can still be solved. Then they remove another number and test it again. Once they reach the point where they can’t remove a number and still have the puzzle be solve’able its done. Thats it. Its horribly simple isn’t it.
I am vaguely reminded of the fiat shamir zero knowledge test. (which is anything but horribly simple) If you look at the problem from one direction, (trying to create the puzzle from scratch, or trying to calculate a secret key) it is virtually impossible. Not totally impossible, but the math required is either out of our reach or just so complicated it would take a computer years to finish. Turn the problem on its head and its easy. (creating a puzzle from the solution, or checking if an already known key is valid)
Its an interesting idea. Perhaps more of life’s problems can be solved by going about things the wrong way…
Filed in Uncategorized |