Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

isomorphic sudoku to consider searching for 17 or 16 sudoku

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
leeo

Joined: 24 Jun 2009
Posts: 6
:
Location: USA NW

Items
PostPosted: Fri Jun 26, 2009 1:23 pm    Post subject: isomorphic sudoku to consider searching for 17 or 16 sudoku Reply with quote

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".
Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 408
:
Location: NJ USA

Items
PostPosted: Fri Jun 26, 2009 1:41 pm    Post subject: Re: isomorphic sudoku to consider searching for 17 or 16 sud Reply with quote

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
Back to top
View user's profile Send private message Visit poster's website
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Tue Jun 30, 2009 10:19 pm    Post subject: Reply with quote

when subject to minimum lexographic representation this is the equivalent of your pattern.
Code:
........1........2........3........4........5........6........7........8127458369

there are 81 of these patterns in every grid
counts from 10000 random grids, I found only 5 essentially different patterns,
Code:
........1........2........3........4........5........6........7........8123478569 #1# - 410
........1........2........3........4........5........6........7........8124378569 #2# -1345
........1........2........3........4........5........6........7........8124578369 #3# -4864
........1........2........3........4........5........6........7........8127458369 #4# -1143
........1........2........3........4........5........6........7........8147258369 #5# -2238

I can forsee that most grids will have most if not all of these patterns in the 81.

It would be a rare grid that didnt have #3# [eg MC grid]

As to whether it would help getting more 17s ?

Well we would have 48500+ x 81 17-puzzles , with 5 classes.

We would have a potential board with significantly less options [from the fixed clues]
The fixed clues would make the other clues come together to an extent.

Unfortunatly I doubt if it will help to get new 17s......

C
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron