isomorphic sudoku to consider searching for 17 or 16 sudoku

leeo

I've been experimenting with what transformations you can apply to a sudoku and still leave it with the same solutions technique.

First, since the clue numbers are merely place values, performing a permutation on the number set would not change the solution methods. A permutation is merely a mapping from one set to itself: i.e.

{ 1, 2, 3, 4, 5, 6, 7, 8, 9 } ->
{ 1, 4, 2, 8, 5, 7, 3, 6, 9 }

though it is more useful to employ cycle notation

( 2, 4, 8, 6, 7, 3 )

To read the notation, note that 2 maps to 4 which maps to 8, which maps to 6, which maps to 7, which maps to 3, which maps back to 2.

Second, changing the order of rows or columns won't change the solution set or method required, as long as the rows or columns changed are in the same box. Thus we could for example exhange rows 2 and 3 with no problem, but not rows 3 and 4, since the rows belong to different boxes.

Third, changing the order of chutes or towers won't change the solution set or method. Thus, for example, column 4, 5 and 6 could be exchanged for columns 7, 8, and 9, provided they are all done together.

Fourth, transposing the matrix describing the sudoku clues won't change the solution set. This is where rAcB is exchanged for rBcA everywhere in the puzzle.

This is all of the basic matrix transformations, and all the puzzle transformations I could find. For example, the effect of rotating the puzzle to the left by 90-degrees could be described as:

transpose, then
exchange chute 1 and 3 {rows 1,2,3 with rows 7,8,9}
exchange rows 1 and 3
exchange rows 4 and 6
exchange rows 7 and 9

One interesting exercise of all this is to apply these transformations to fix as many of the cells as possible. I can usually fix 17 cells to be of the form

1 6 7 | 2 8 9 | 3 4 5
2 o o | o a b | o c d
3 o o | o o o | o o o
------+-------+-------
4 o o | o o o | o o o
5 o o | o o o | o o o
6 o o | o o o | o o o
------+-------+-------
7 o o | o o o | o o o
8 o o | o o o | o o o
9 o o | o o o | o o o

it is also a simple matter to apply transformations so that a < b and c < d. I have not been able to prove that every puzzle can be transformed in this manner, and indeed I have found some puzzles that I have not been able to transform. -- indeed I have found this transformation problem to be more challenging in many respects than solving the sudoku. I challenge any more capable mathematicians to prove that such a transformation is always possible.

Working with puzzles transformed in this manner is just as challenging as working with the untransformed puzzles, provided you do not employ any of the knowledge that the you have the solutions in the first row and column. Here's an example:

cexpert651rating239
1 x x | x 8 9 | x x x
x x 5 | 1 x x | x 6 x
x 8 x | 4 x x | x 2 x
------+-------+-------
x 7 2 | x x x | x 3 x
x x x | x 4 3 | x x 6
x x x | x x x | 9 x x
------+-------+-------
x 3 6 | 8 x x | x x x
8 x x | x x 5 | x x 3
9 x x | x 1 x | x x 7

These puzzles work great for debugging solvers, since it is easier to navigate at a glance, since the first column "labels the rows".

gsf

search for { minlex canonical canonicalization c14n } on the programmers and players forums
both forums have pretty much settled on row-order minlex as the canonical form

coloin · Posted: Tue Jun 30, 2009 10:19 pm Post subject:

when subject to minimum lexographic representation this is the equivalent of your pattern.