FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Canonicalize sudoku puzzle          Sudoku Programmers Forum Index -> Programming sudoku View previous topic :: View next topic   Author Message dmhayden Joined: 01 Aug 2007 Posts: 16 : Location: Central New Jersey Items Posted: Mon Apr 14, 2008 8:14 pm    Post subject: Canonicalize sudoku puzzle There's a discussion in another thread about seeing if a puzzle with 17 givens is in a known list. This requires canonicalizing the puzzles to ensure that the new puzzle isn't a simple transformation of one of the known puzzles. Is there a standard method for canonicalizing puzzles? I'd like to add this to my solver so I'm looking for a description of the process, not a program that does it. Thanks, Dave Back to top Sisophon2001 Joined: 05 Mar 2008 Posts: 32 : Location: Cambodia Items Posted: Tue Apr 15, 2008 9:00 am    Post subject: The nest reference I have found is here on this forum. Use the search function for canonicalize and go back to the first post. You will find lots of discussion and VB source code. Garvan Back to top daj95376 Joined: 05 Feb 2006 Posts: 349 : Items Posted: Tue Apr 15, 2008 10:47 am    Post subject: Sisophon2001 wrote: The nest reference I have found is here on this forum. Use the search function for canonicalize and go back to the first post. You will find lots of discussion and VB source code. I would not make that recommendation. There has been some heavy discussion on canonicalization (c14n) in this and the Players' forum within the last year. I do not believer that the older c14n algorithms are used anymore. dmhayden needs an algorithm that conforms to this standard grid. Code:            MinLex  +-----------------------+  | 1 2 3 | 4 5 6 | 7 8 9 |  | 4 5 . | . . . | . . . |  | . . . | . . . | . . . |  |-------+-------+-------|  | 2 . . | . . . | . . . |  | . . . | . . . | . . . |  | . . . | . . . | . . . |  |-------+-------+-------|  | . . . | . . . | . . . |  | . . . | . . . | . . . |  | . . . | . . . | . . . |  +-----------------------+ Back to top dmhayden Joined: 01 Aug 2007 Posts: 16 : Location: Central New Jersey Items Posted: Tue Apr 15, 2008 2:04 pm    Post subject: Thanks Daj! The standard grid gives me most of what I need. From what I've read, you can make the following transformations: - swap two stacks of boxes - swap two column within a single stack - swap two horizontal groups of boxes - swap two rows within a a horizontal group of boxes - rotate puzzle around the center - rotate around the diagonals - remap the numbers. Are any of these transformations degenerate cases of the others? Thanks again, Dave Back to top daj95376 Joined: 05 Feb 2006 Posts: 349 : Items Posted: Tue Apr 15, 2008 2:59 pm    Post subject: dmhayden wrote: Thanks Daj! The standard grid gives me most of what I need. From what I've read, you can make the following transformations: - swap two stacks of boxes - swap two column within a single stack - swap two horizontal groups of boxes - swap two rows within a a horizontal group of boxes - rotate puzzle around the center - rotate around the diagonals - remap the numbers. Are any of these transformations degenerate cases of the others? You'll need for gsf or one of the other veterans of the forum to answer this question. I know that they have a link to a post that answers your question perfectly. Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Tue Apr 15, 2008 4:07 pm    Post subject: daj95376 wrote: dmhayden wrote: From what I've read, you can make the following transformations: - swap two stacks of boxes - swap two column within a single stack - swap two horizontal groups of boxes - swap two rows within a a horizontal group of boxes - rotate puzzle around the center - rotate around the diagonals - remap the numbers. Are any of these transformations degenerate cases of the others? You'll need for gsf or one of the other veterans of the forum to answer this question. I know that they have a link to a post that answers your question perfectly. this thread goes through the details but the early parts refer to a slightly different form the two prevalent forms now are both minlex by row from top left to bottom right i.e., form an 81 digit number and do the normal row/col/transpose/renumber ops to make the smallest possible number in my solver the default canonicalization (solution-minlex) is based on the solution grid of the puzzle, so it only works for valid sudoku the alternate canonicalization (puzzle minlex) is based on the minlex of the puzzle, so it works on puzzles with multiple solutions or on bands too solution-minlex is more efficient ruud has another c14n algorithm (pattern-minlex?) that first treats the clues as value 1 and empty cells as value 0 and determines the boolean-minlex then it determines the minlex value mapping the symmetry operations are Code: 1. Relabel (i.e., permute) the 9 digits; 2. Permute the three stacks; 3. Permute the three bands; 4. Permute the three columns within a stack; 5. Permute the three rows within a band; 6. transposition from Sudoku Symmetry Formalized Back to top coloin Joined: 05 May 2005 Posts: 97 : Items Posted: Tue Apr 15, 2008 7:13 pm    Post subject: The topic canonical form is an interesting and relevant read. In it Mauricio suggested and questioned: Code: It is easy to see what daj95376/JPF say. It is harder to see that every sudoku grid is isomorph to a grid with the following 18 fixed cells: 123|...|... 456|12.|... 789|...|1.. ---+---+--- .1.|...|... ...|.1.|... ...|...|.1. ---+---+--- ..1|...|... ...|..1|... ...|...|..1   The difficult part is to see that we can set r2c5=2. Proof: First fix the 1's and relabel the numbers in the first box, so that they match the proposed solution, now we want to set r2c5=2. We analize the possible places to put 2 and 3 in box 2: 1. If r2c5=2, good, we are done. 2. If r2c6=2, then: 2.1 If r3c8=2, then do r123456789 c123456789 -> r132465798 c123789456 and relabel accordingly so now r2c5=2. 2.2 If r3c9=2 then do r123456789 c123456789 -> r231564897 c465798132 and relabel accordingly. 3. If r2c5=3 or r2c6=3 then swap columns 2 and 3 and relabel so now that 3 is a 2, now we are in a case that has been covered in steps 2.1 and 2.2. 4. If r2c5<>2,3 and r2c6<>2,3, then we start again, but instead of fixing the 1's, we fix the 2's and we are done (after that litle work is needed here). In daj95376/JPF example there are 17 fixed cells, I showed that we can fix 18 cell's. Can we fix more than 18 cells? I think we probably can as the solution count for this is way more thn 5*10^9. The reason to do it ? Well, in this thread we are attempting to add 5 different clues to a selection of equivalent 12 clue subpuzzles. [to get a new 17] Using the minlex form of the soluton grid and the resultant puzzle we can get some help from fixed clues. In Mauricios example there are many more clues......is this a better grid to use ? Are there more clues to add ? There must be ? My punt Code: 123|...|... 456|12.|... 789|...|1.. ---+---+--- .1.|...|... ...|.12|... ...|...|.1. ---+---+--- ..1|...|... ...|2.1|... ...|...|..1 How many grids dont have this type of 6 clue unavoidable ? Whilst we are at it why dont we throw in a 4 clue unavoidable ! C Back to top wapati Joined: 12 Jun 2007 Posts: 622 : Location: Canada Items Posted: Tue Apr 15, 2008 9:11 pm    Post subject: dmhayden wrote: Thanks Daj! The standard grid gives me most of what I need. From what I've read, you can make the following transformations: - swap two stacks of boxes - swap two column within a single stack - swap two horizontal groups of boxes - swap two rows within a a horizontal group of boxes - rotate puzzle around the center - rotate around the diagonals - remap the numbers. Are any of these transformations degenerate cases of the others? Thanks again, Dave I am thinking you can make it a lot simpler for yourself. Rotate 90 degrees is allowed. Because of this you can cut in half your concerns in coding. - swap two stacks of boxes - swap two column within a single stack The above when rotated 90 deal with rows/chutes. I am very suspicious of your "- rotate around the diagonals". That's my penny spent! Back to top tarek Joined: 31 Dec 2005 Posts: 153 : Location: London, UK Items Posted: Thu Apr 17, 2008 3:21 pm    Post subject: gsf wrote: ruud has another c14n algorithm (pattern-minlex?) that first treats the clues as value 1 and empty cells as value 0 and determines the boolean-minlex then it determines the minlex value mapping Ruud's puzzle/pattern c14n algorithm is great...... It would have been even better if adopted the following: 1. treat the clues as value 1 and empty cells as value 0 2. find boolean-minlex of highest dihedral symmetry 3. minlex value mapping This is something that can be added to your solver gsf tarek Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Thu Apr 17, 2008 3:33 pm    Post subject: tarek wrote: 1. treat the clues as value 1 and empty cells as value 0 2. find boolean-minlex of highest dihedral symmetry 3. minlex value mapping This is something that can be added to your solver gsf something close to this would be good for generating patterns game submissions: determine the minlex mapping for a given pattern this would help prune a comprehensive search in a way similar to the enumeration of all solution grids don't have the code visualized yet Back to top enxio27 Joined: 10 Feb 2007 Posts: 12 : Items Posted: Mon May 19, 2008 9:13 pm    Post subject: I've read a lot of the discussion on canonicalization, and I've been to Gordon's and Glenn's Web sites, but the more I read, the more confused I get. (For one thing, there is a lot of jargon there that I'm unfamiliar with.) Can someone give me a step-by-step on HOW to canonicalize a given puzzle? I've seen the algorithms, but I'm not sure how to make use of them. I've dabbled in programming in a number of languages, but haven't really mastered any of them. I do understand basic programming concepts, though. Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Programming sudoku All times are GMT Page 1 of 1   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  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   Powered by phpBB © 2001, 2005 phpBB Group Igloo Theme Version 1.0 :: Created By: Andrew Charron