I’ve been researching others’ techniques for generating sudoku puzzles, and I have come to the conclusion that nobody actually knows how to do it.
Seriously, if you Google for “generating sudoku puzzles”, most of the methods boil down to “randomly throw numbers at the board and see if it’s a sudoku”. Oh, there’s some cleverness you can do to try to intelligently preserve the randomness of a partially-complete sudoku puzzle (like not randomly putting a 9 into a column that already has one) but at the end of the day all of the solutions basically amount to bogosort.
I promised yesterday that I’d reveal the identity board math. I had planned a big reveal here with lots of mathy explanationing, but the math just isn’t that exotic. There’s a trick to it, but that’s about it. Here’s the math:
A Sudoku board of dimension n is n2xn2 digits, and has nxn sectors, each with n2 digits. Let’s write a function to find the number at position x, y on the board. The whole trick to my F(x,y) math is simply this: the numbers in every sector other than (0,0) are rotations or shifts of the numbers in sector (0,0).
Make sense? Here. The numbers in sector(0,0) are simply the digits 1..n2, arranged in a grid, so that’s easy:
F(x,y): y*n+x
And the math for every other sector is simply a selection into sector 0, 0. Specifically, for F(x,y) outside of sector (0,0), choose the F(x’,y’) IN sector 0,0 such that
x’ = ((x+y/n)%n
y’ = ((y+x/n)%n
So at the end of the day the whole function looks like this in ruby:
def idfx(x, y, n)
if x<n && y<n
y*n+x
else
idfx( ((x+y/n)%n, ((y+x/n)%n )
end
end
I should point out that I am operating under the belief that a sudoku puzzle is like a Rubik’s Cube: that a set of transformations can be performed on a valid puzzle that leave the puzzle changed but always valid, and that you can turn any sudoku puzzle into any other sudoku puzzle via these transformations. If I am right, I can take my identity puzzle board and shuffle it using these transformations, and just like scrambling a Rubik’s Cube I will be left with a unique and interesting puzzle that is, most importantly, still valid.
I have proven the first half of my assumption–there are transformations that will change a sudoku without affecting its validity. What I haven’t proven is the second half. I cannot yet transform puzzles arbitrarily. It may not be possible at all, but right now I’m simply hoping that I don’t know enough transformations yet.
Why, Dave, Why 
Very cool, thank you. It’s going to take me a long bit of studying to be able to understand most of those sentences. Heh.
The project manager in me, however, says: okay, given those assumptions, we cannot get from A to B. Assuming it is a requirement to get from A to B, what assumptions have to change? And to stay true to the original intent, without resorting to bososort?
Two questions immediately spring to mind: Are there OTHER transformations that will produce the effect of exchanging a handful of cells, and are there transformations that will move a board directly from equivalency class to another.
No, I’m not proposing storing off 5 gigs of transformations; I’m just hoping to find some underlying structure.
It’s 1am and I’m about to toddle to bed, but re: the Rubik’s Cube, my assertion is sloppily phrased so I am hesitant to defend it.
But yes–if you disassemble a cube and reassemble it solved but twist exactly one corner piece, the cube will forever be unsolvable without another reassembly. The “parity” of the cube is changed, if you will.
I’m thinking fuzzily here (not good with math, I know) but it seems like you could make the argument that a Rubik’s cube with a twisted corner is like an invalid sudoku. The twisted corner would be like having two 3’s in a single sector, etc. OTOH, your point is clear that the standard transitions are insufficient to move from the solved superposition to the corner-twist superposition. But on the Gripping Hand, moving from one sudoku equivalency to another by direct transformation could be considered a valid transformation in exactly the same way that disassembling your cube might be a valid transfer function….
Heh. Okay ow. Sleepy head hurt now. 🙂
Hi Chris! I think so. The trick lies in un-shuffling the board using my base transformations (swap rows, swap lines, swap digits, etc). I think–but cannot prove–that if you can always reduce the upper-left 3×3 cell into a sorted 1..9 cell. Then, because you can swap big rows and big columns pretty much willy nilly, you should be able to kind of “sort” the board’s 3×3 cells. Let’s call this sorted board the “identity” board for that arrangement.
There are two problems with this, though: the first is that I do not actually know if this is possible. The second is that once reduced to an identity board, there are still 5 *billion* identity boards. So while you could compare two boards for identity equivalence, you probably could not meaningfully look at a set of identity boards and recognize them.
And a third problem, that I just thought of right now, is that you could not compare identities until after you’d solved the board anyway, so the only real advantage to knowing this is in outing a lazy board designer, not in actually solving the boards themselves.
Thanks for the comment!
Oh, also, a board’s difficulty does not lie in its identity arrangement, but rather in how much of the board is obscured to start. Apparently the crazy master-level sudoku have no obvious digits, you have to play logic games like knowing that the same trio of numbers is spread across 4 cells, etc. The really good sudoku board generators will “play” these moves in reverse, using more and more advanced moves to remove numbers yet still leave the board with one single provable solution.
So… yeah. I guess you COULD just reuse the same board over and over again. Heh.