FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Unique puzzle Goto page 1, 2  Next          Sudoku Programmers Forum Index -> Setting sudoku View previous topic :: View next topic   Author Message tarek Joined: 31 Dec 2005 Posts: 153 : Location: London, UK Items Posted: Mon Jan 30, 2006 3:22 pm    Post subject: Unique puzzle Just to make sure that no puzzles are actually the same in my database, I've tried to adopt the methods that would ultimately reconfigure the puzzle to produce a Normalized (I'm not sure what the proper word is), similar to what G Royle has used in his minimum sudoku. does anyone know what factors determine Transposing the matrix (Exchanging rows and columns) or not? Back to top eclark Joined: 28 Dec 2005 Posts: 70 : Items Posted: Mon Jan 30, 2006 3:36 pm    Post subject: This is something I too would really love. Basically I am starting to put together what I hope will be a great database of puzzles and I want to know how to "normalize" all of them. Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Mon Jan 30, 2006 4:26 pm    Post subject: eclark wrote: This is something I too would really love. Basically I am starting to put together what I hope will be a great database of puzzles and I want to know how to "normalize" all of them. my command line solver provides -f%C option to print the canonical solution and -f%c to print the original puzzle in canonical order you can use %C as a key to group puzzles generated from the same grid and %c as a key for puzzle equality up to isomorphism I use -f'%C %c' in my catalogs the canonical form is the lexicographically smallest digit string of cell values when read from top to bottom, left to right, with box 1 (upper left) fixed to Code: 1 2 3 4 5 6 7 8 9 generated by applying row/col permutations and cell value reassigments for example, this pipeline identifies the canonical "strangely familiar" grid from gordon's 17 catalog (29 17's from one grid) along with the grids that contain { 11 12 14 20 } 17's Code: sudoku -f%C sudoku17.dat | sort | uniq -c | grep -v '^ *[^ ] ' | sort -n Back to top eclark Joined: 28 Dec 2005 Posts: 70 : Items Posted: Mon Jan 30, 2006 4:34 pm    Post subject: Great thanks. The re-numbering of the top left box was about what I am currently coding up. As I see it basically just renumbering is all that is needed to create this base reference canonical solution. Then I can test all subsequesnt generated puzzles to see if they can be made into this base layout. Thanks. Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Mon Jan 30, 2006 4:58 pm    Post subject: eclark wrote: Great thanks. The re-numbering of the top left box was about what I am currently coding up. As I see it basically just renumbering is all that is needed to create this base reference canonical solution. {2006-01-30 edit -- forgot rotational symmetry check} its a combination of all four row permutations col permutations row/col swap for rotational symmetry cell relabeling where the row/col permutations include band permutations e.g., the top 3 rows can be swapped with the bottom 3 rows the key to the algorithm is fixing the top left box that limits the lexicographic search to boxes rather than rows/cols or cells but the search must include all boxes and all permutations/labelings within the fixed box Last edited by gsf on Mon Jan 30, 2006 5:20 pm; edited 1 time in total Back to top tarek Joined: 31 Dec 2005 Posts: 153 : Location: London, UK Items Posted: Mon Jan 30, 2006 5:00 pm    Post subject: gsf, I've managed to program all of what you mentioned, what about the the aspect dealing with my 1st post. to ensure ROTATIONAL uniqueness. When should we do all of the mentioned permutations after Exchanging every row with every column? (i.e. 90 degree rotation) Tarek Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Mon Jan 30, 2006 5:18 pm    Post subject: tarek wrote: I've managed to program all of what you mentioned, what about the the aspect dealing with my 1st post. to ensure ROTATIONAL uniqueness. When should we do all of the mentioned permutations after Exchanging every row with every column? (i.e. 90 degree rotation) right swapping rows/cols should have been mentioned as another operation basically double the outer loop one time in row order, the other time in col order Back to top tarek Joined: 31 Dec 2005 Posts: 153 : Location: London, UK Items Posted: Mon Jan 30, 2006 5:22 pm    Post subject: gsf wrote: right swapping rows/cols should have been mentioned as another operation basically double the outer loop one time in row order, the other time in col order So you have 2 versions for each puzzle. Isn't there a way to produce the same 1 final puzzle regardless of how rotated it is??? Back to top eclark Joined: 28 Dec 2005 Posts: 70 : Items Posted: Mon Jan 30, 2006 5:31 pm    Post subject: Thanks gsf. You are a great reference to this forum. I think I have it now. Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Mon Jan 30, 2006 5:35 pm    Post subject: tarek wrote: So you have 2 versions for each puzzle. Isn't there a way to produce the same 1 final puzzle regardless of how rotated it is??? adding in row/col swap for rotation just doubles the search space for the best lexicographic ordering there's still only one outcome let the grid cells be indexed from 0..80 the canonical ordering is an array order[0..80] that produces the canonical index for each cell the order[] array can encode all operations but relabeling which requires another array label[1..9] Back to top tarek Joined: 31 Dec 2005 Posts: 153 : Location: London, UK Items Posted: Mon Jan 30, 2006 5:42 pm    Post subject: gsf wrote: adding in row/col swap for rotation just doubles the search space for the best lexicographic ordering there's still only one outcome Thanx gsf, I know that there will be always the same result for reflections & 180 rotations, but is it the same for 90 degrees rotation? The impression that I got from surfing seems to be that it is not, I'll take your word for it Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Mon Jan 30, 2006 6:47 pm    Post subject: tarek wrote: gsf wrote: adding in row/col swap for rotation just doubles the search space for the best lexicographic ordering there's still only one outcome I know that there will be always the same result for reflections & 180 rotations, but is it the same for 90 degrees rotation? The impression that I got from surfing seems to be that it is not, I'll take your word for it there's a disconnect somewhere the canonical ordering must take into account 90 deg rotation and all other symmetry transforms and cell relabeling Back to top tarek Joined: 31 Dec 2005 Posts: 153 : Location: London, UK Items Posted: Mon Jan 30, 2006 8:58 pm    Post subject: gsf wrote: there's a disconnect somewhere the canonical ordering must take into account 90 deg rotation and all other symmetry transforms and cell relabeling Yes it should, but the method you just described produces 2 different canonical orderings, one for columns & one for rows (I Think ) The output from your program is which one ? if it takes into consideration both aspects to produce 1 final answer, how is that done? you mentioned running the program in 2 loops (one for columns & one for rows), to me that means 2 different end results, if the result per loop is always the same, why bother doing both? Back to top eclark Joined: 28 Dec 2005 Posts: 70 : Items Posted: Mon Jan 30, 2006 10:07 pm    Post subject: Ok so we are trying to find the answer that is as close as possible to 12345678912345..... as possbible ? or am I tottally off ? Here is what I am looking at. Code: 5..|.74|... ...|2..|6.. ...|..5|34. ---+---+--- ...|...|8.. 3..|.8.|516 .8.|..3|... ---+---+--- 6.4|.5.|... ...|1..|2.. 9..|6.2|..3 12C|DEF|7HI D5F|GH9|A32 GHI|B3A|ED6 ---+---+--- BF4|HAE|C9G C9H|672|4EA EAG|I4C|FBH ---+---+--- FCE|19H|B7D HDA|E2G|IF3 I7B|CFD|81E 563|974|128 847|231|695 291|865|347 ---+---+--- 459|716|832 372|489|516 186|523|479 ---+---+--- 624|357|981 735|198|264 918|642|753 The first one is the puzzle. The second one is what your program returns as the canonical order. The third/last is the answer to the puzzle. can someone help walk me through putting this in canonical order ? Blah sorry I haven't felt so lost at this in a while Back to top tarek Joined: 31 Dec 2005 Posts: 153 : Location: London, UK Items Posted: Mon Jan 30, 2006 10:41 pm    Post subject: The setting you chose eclark is probably for a 16*16 sudoku, you should only have 1-9 in a 9*9 sudoku returning to the issue of 90 rotation: here is eclarck's puzzle: Code:  . . . | . 6 . | . . 3   . . 4 | . 1 . | . . .   . 6 3 | 8 5 . | . 2 .  -------+-------+------  4 . 5 | . . 3 | . . 2   7 . . | . 8 . | 5 . .   . 2 . | . . . | . 1 6  -------+-------+------  . . . | . . . | 4 . .   . . . | . . 8 | . . .   5 . . | . 3 . | 6 . 9 & here is it is canonical form as I see it: Code:  . . . | . . 8 | . . 9   . . 6 | . . 7 | . . .   . 8 9 | 1 . 2 | 4 . .  -------+-------+------  3 . . | . . 1 | . 2 .   . 4 . | . . . | 7 . 8   6 . 2 | . 9 . | . . 4  -------+-------+------  2 . . | . . 9 | . 8 5   . . . | . 1 . | . . .   . . . | . . . | . 6 . now rotating everything 90 degrees we get: Code:  5 . . | . 7 4 | . . .   . . . | 2 . . | 6 . .   . . . | . . 5 | 3 4 .  -------+-------+------  . . . | . . . | 8 . .   3 . . | . 8 . | 5 1 6   . 8 . | . . 3 | . . .  -------+-------+------  6 . 4 | . 5 . | . . .   . . . | 1 . . | 2 . .   9 . . | 6 . 2 | . . 3 & the canonical form of: Code:  1 . . | 5 6 . | . . .   . . . | . . 7 | . . 2   . . . | 1 . . | . 5 3  -------+-------+------  2 . 5 | . 1 . | . . .   . . . | . . 9 | . . 7   8 . . | 7 . 2 | 3 . .  -------+-------+------  3 . . | . 4 . | 2 9 1   . . . | . . . | . . 4   . 4 . | 3 . . | . . .  it is the same puzzle but with 2 results. Hw could we have 1 distinctive result ???? Would you rearrange then relabel, I'm a bit puzzled here myself???? Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Setting sudoku All times are GMT Goto page 1, 2  Next Page 1 of 2   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