Isomorphic sudokus
When mathematicians count the 5,472,730,538 possible sudokus, they count the diagrams above as one sudoku, not two. The sudokus are said to be isomorphic because one can be transformed into the other by rearranging the rows and columns and relabeling the digits without disturbing the essential “sudoku property” that every row, column and block consists of 1 through 9. Since the sudoku property doesn’t change, it’s still the “same” sudoku pattern.
Well, this makes sense in an abstract, mathematical way, but what does it feel like to the person solving the sudoku? I decided to find out. I printed out the two puzzles and solved them. There are some similarities that relate to the way I solve puzzles. For example, both diagrams have two columns with 5 cells filled in, and there are often opportunities to complete such columns. Both diagrams have one row with a single element, and I tend to avoid such rows.
I knew that the sudokus were isomorphic, so it was easy to pick up on a few similarities. Even so, solving one didn’t make it any easier to solve the other, and if I hadn’t set up the isomorphism myself, I never would have suspected.
It’s tempting to conclude that the human sudoku solver does not solve the underlying abstract sudoku, he solves the particular representation in front of him. This is not quite right, because I think I would notice something simple, for example if the two diagrams were identical except for the 6s and 9s being switched around.
On the other hand, now when I find a particularly good source of puzzles (like the “evil” Times of Malta sudoku on Sundays), I can run them through my rearranger and make several puzzles out of each one.
June 28th, 2009 at 6:06 pm
So wouldn’t there be only one “essential sudoku property” since you can rearrange rows, columns and icons.
Or do you mean that as long as you retain the same number of icons in each row and each column you can rearrange them to your heart’s content?
If you start with a filled in sudoku, and remove one icon, would all 81 versions of it with one icon removed be considered the same sudoku?
June 28th, 2009 at 6:50 pm
By “rearrange rows” I mean things like “swap row 2 and row 3″. You can’t rearrange cells within a row unless it’s a side effect of swapping two columns. Note that you can swap row 2 and row 3, but you can’t swap row 3 and row 4, because that would mess up the blocks.
As to the last question, if you remove one cell (any single cell), it’s still the same sudoku because there’s only one digit that can go in that cell, and it doesn’t matter whether it’s written down. If you remove so many cells that there is more than one way to solve the puzzle, then it’s not the same sudoku any more.
July 4th, 2009 at 8:46 pm
If you had a crocheted sudoku in thin white thread and stitched it together top to bottom to make a tube of the horizontal rows and then starched it nice and crisp it makes sense that the rows could be moved about and the same relationships would exist - but I can’t picture it. Can you duplicate that with the computer?
Also, if you stitched them so the left and right sides were connected. I also cannot visualize both things happening at the same time - it seems to me that that exists in an additional dimension.
July 5th, 2009 at 2:42 pm
If you make a tube and then connect the left and right, you get a torus… the surface of a donut or inner tube. (A sudoku pattern on an inner tube would be a nice pool toy.)
The surface is still two-dimensional, but we have to embed it in a three-dimensional space to look at it from outside. A sudoku pattern (or any square grid) will fit on a torus. The cells are still squarish in that they have 4 sides meeting at right angles, but the sides won’t all be the same length. If you try to cover a sphere with a square grid, the squares get squeezed into triangles at the poles. Replace the poles with a hole, and the grid fits.