FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Table Solving Goto page Previous  1, 2          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message MadOverlord Joined: 01 Jun 2005 Posts: 80 : Location: Wilmington, NC, USA Items Posted: Sun Aug 28, 2005 11:52 pm    Post subject: AMcK wrote: I also tried the suggested "unverity" and "unveracity" algorithm where any deductions common to at least two negative candidates in a cell or possibles in a house must be true. [Proof: since only one candidate can be true, at least one of any pair must be false and so any common implications must be from at least one correctly false assumption]. I got some hits for unverities but I'm still not convinced that this increases the power of the solver. IIRC, in tabling at least, the negative verities and veracities don't generate extra insights into the puzzle, but they are sometimes easier to see and compute than the positive type. This is because negative assertions tend to have fewer implications. Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Mon Aug 29, 2005 12:26 am    Post subject: Here's a simple ultracolourable puzzle from my generator. Code: . . 4 ¦ . 5 8 ¦ 2 7 . 5 . . ¦ . 1 . ¦ . 9 . . . . ¦ 2 . . ¦ . 5 6 ------+-------+------- . . . ¦ 5 6 . ¦ . . . 2 . . ¦ . . 4 ¦ 1 6 8 . . . ¦ . 9 2 ¦ . . . ------+-------+------- 1 5 . ¦ . 2 6 ¦ . . . . 4 . ¦ . 8 . ¦ . . 2 . 2 8 ¦ 4 7 . ¦ 6 . . Contains a mixture of contradictions, verities, veracities and unverities, depending on whether you apply standard rules before starting. Regards Andrew Back to top MadOverlord Joined: 01 Jun 2005 Posts: 80 : Location: Wilmington, NC, USA Items Posted: Mon Aug 29, 2005 12:50 am    Post subject: It's a toughy, but Nishio and Forcing Chains cracks it. Code: Deduction pass 1; 32 squares solved; 49 remaining. * The following immediate observations can be made:   R5C5 must be <3>. From this deduction, the following moves are immediately forced:    R5C4 must be <7>.    R3C5 must be <4>.    R5C2 must be <9>.    R4C6 must be <1>.    R6C4 must be <8>.    R5C3 must be <5>. Deduction pass 2; 39 squares solved; 42 remaining. * R2C3 is the only square in row 2 that can be a <2>.  It is thus pinned to that value. Deduction pass 3; 40 squares solved; 41 remaining. * R4C8 is the only square in row 4 that can be a <2>.  It is thus pinned to that value. Deduction pass 4; 41 squares solved; 40 remaining. * R8C4 is the only square in column 4 that can be a <1>.  It is thus pinned to that value. From this deduction, the following moves are immediately forced:    R8C8 must be <3>.    R6C8 must be <4>.    R9C8 must be <1>.    R7C8 must be <8>. Deduction pass 5; 46 squares solved; 35 remaining. * R4C1 is the only square in row 4 that can be a <4>.  It is thus pinned to that value. Deduction pass 6; 47 squares solved; 34 remaining. * R4C2 is the only square in row 4 that can be a <8>.  It is thus pinned to that value. Deduction pass 7; 48 squares solved; 33 remaining. * R2C7 is the only square in row 2 that can be a <8>.  It is thus pinned to that value. From this deduction, the following moves are immediately forced:    R3C7 must be <3>.    R1C9 must be <1>.    R2C9 must be <4>. Deduction pass 8; 52 squares solved; 29 remaining. * R3C1 is the only square in row 3 that can be a <8>.  It is thus pinned to that value. Deduction pass 9; 53 squares solved; 28 remaining. * R7C7 is the only square in row 7 that can be a <4>.  It is thus pinned to that value. Deduction pass 10; 54 squares solved; 27 remaining. * Found a Nishio contradiction.  After 2 cycles, it became clear that R6C9 could not be a <7>.    R6C9 - removing <7> from <357> leaving <35>.   Here is a trace of the Nishio matrix as it was simplified.    # = Squares that must be <7>.    O = squares that can be a <7>.    X = the current square (also an "O").    . = squares that cannot be <7>.    - = squares that were invalidated in the previous cycle.    P = the square that invalidated them (also a "#").    @ = the invalid group that cannot contain a <7>.   Nishio cycle 1 on <7> at R6C9    . . . . . . . # .    . O . . . O . . .    . O O . . O . . .    . . O . . . O . O    . . . # . . . . .    O O O . . . O . X    . . O . . . . . O    O . O . . . O . .    . . . . # . . . .   Nishio cycle 2 on <7> at R8C7    . . . . . . . # -    . O . . . O . . -    . O O . . O . . -    . . O . . . - - -    . . . # . . - - -    - - - - - - - - P    . . O . . . . . -    O . O . . . X . -    . . . . # . . . -   Final State:    @ . . . . . - # .    @ O . . . O - . .    @ O O . . O - . .    @ . O . . . - . .    @ . . # . . - . .    @ . . . . . - . #    @ . O . . . - - -    @ - - - - - P - -    @ . . . # . - - - Deduction pass 11; 54 squares solved; 27 remaining. * Found a forcing chain.  If we assume that square R6C1 is <3> then we can make the following chain of conclusions:    R6C9 must be <5>, which means that    R9C9 must be <9>, which means that    R9C1 must be <3>, which means that    R6C1 must be <67>. Since this is logically inconsistent, R6C1 cannot be <3>. Deduction pass 12; 54 squares solved; 27 remaining. * Found a Nishio contradiction.  After 2 cycles, it became clear that R1C4 could not be a <3>.    R1C4 - removing <3> from <369> leaving <69>.   Here is a trace of the Nishio matrix as it was simplified.    # = Squares that must be <3>.    O = squares that can be a <3>.    X = the current square (also an "O").    . = squares that cannot be <3>.    - = squares that were invalidated in the previous cycle.    P = the square that invalidated them (also a "#").    @ = the invalid group that cannot contain a <3>.   Nishio cycle 1 on <3> at R1C4    O O . X . . . . .    . O . O . O . . .    . . . . . . # . .    . . O . . . . . O    . . . . # . . . .    . O O . . . . . O    . . O O . . . . .    . . . . . . . # .    O . . . . O . . .   Nishio cycle 2 on <3> at R9C6    - - - P - - - - -    . O . - - - . . .    . . . - - - # . .    . . O - . . . . O    . . . - # . . . .    . O O - . . . . O    . . O - . . . . .    . . . - . . . # .    O . . - . X . . .   Final State:    @ . . # . - . . .    @ O . . . - . . .    @ . . . . - # . .    @ . O . . - . . O    @ . . . # - . . .    @ O O . . - . . O    @ . O - - - . . .    @ . . - - - . # .    @ - - - - P - - - Deduction pass 13; 54 squares solved; 27 remaining. * Intersection of row 1 with block 1. The value <3> can only appear in squares R1C1, R1C2 and R1C3 of row 1.  Thus, the non-intersecting squares of block 1 cannot contain this value.    R2C2 - removing <3> from <367> leaving <67>. Deduction pass 14; 54 squares solved; 27 remaining. * Found a Nishio contradiction.  After 2 cycles, it became clear that R7C3 could not be a <9>.    R7C3 - removing <9> from <379> leaving <37>.   Here is a trace of the Nishio matrix as it was simplified.    # = Squares that must be <9>.    O = squares that can be a <9>.    X = the current square (also an "O").    . = squares that cannot be <9>.    - = squares that were invalidated in the previous cycle.    P = the square that invalidated them (also a "#").    @ = the invalid group that cannot contain a <9>.   Nishio cycle 1 on <9> at R7C3    O . . O . . . . .    . . . . . . . # .    . . O . . O . . .    . . . . . . O . O    . # . . . . . . .    . . . . # . . . .    . . X O . . . . O    O . O . . O O . .    O . . . . O . . O   Nishio cycle 2 on <9> at R1C1    X . - O . . . . .    . . - . . . . # .    . . - . . O . . .    . . - . . . O . O    . # - . . . . . .    . . - . # . . . .    - - P - - - - - -    - - - . . O O . .    - - - . . O . . O   Final State:    P - - @ - - - - -    - - - @ . . . # .    - - - @ . O . . .    - . . @ . . O . O    - # . @ . . . . .    - . . @ # . . . .    - . # @ . . . . .    - . . @ . O O . .    - . . @ . O . . O Deduction pass 15; 54 squares solved; 27 remaining. * 2 squares in column 3 form a simple locked pair.  R4C3 and R7C3 share possibilities <37>.  Thus, these possibilities can be removed from the rest of the column.    R3C3 - removing <7> from <179> leaving <19>.    R6C3 - removing <37> from <1367> leaving <16>.    R8C3 - removing <7> from <679> leaving <69>. Deduction pass 16; 54 squares solved; 27 remaining. * Intersection of block 1 with column 2. The value <7> can only appear in squares R1C2, R2C2 and R3C2 of block 1.  Thus, the non-intersecting squares of column 2 cannot contain this value.    R6C2 - removing <7> from <1367> leaving <136>. Deduction pass 17; 54 squares solved; 27 remaining. * Found a forcing chain.  If we assume that square R9C9 is <9> then we can make the following chain of conclusions:    R9C1 must be <3>, which means that    R7C3 must be <7>, which means that    R7C9 must be <9>, which means that    R9C9 must be <5>. Since this is logically inconsistent, R9C9 cannot be <9>. From this deduction, the following moves are immediately forced:    R6C9 must be <3>. Deduction pass 18; 56 squares solved; 25 remaining. * R4C3 is the only square in row 4 that can be a <3>.  It is thus pinned to that value. From this deduction, the following moves are immediately forced:    R7C3 must be <7>.    R7C9 must be <9>.    R7C4 must be <3>.    R4C9 must be <7>.    R8C7 must be <7>.    R4C7 must be <9>.    R6C7 must be <5>.    R2C4 must be <6>.    R9C6 must be <9>.    R9C1 must be <3>.    R3C6 must be <7>.    R8C6 must be <5>.    R2C2 must be <7>.    R1C4 must be <9>.    R3C2 must be <1>.    R2C6 must be <3>.    R1C1 must be <6>.    R3C3 must be <9>.    R6C2 must be <6>.    R8C3 must be <6>.    R6C1 must be <7>.    R6C3 must be <1>.    R1C2 must be <3>.    R8C1 must be <9>. Deduction pass 19; 81 squares solved; 0 remaining. Solution found! Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Mon Aug 29, 2005 8:01 am    Post subject: MadOverlord wrote: It's a toughy, but Nishio and Forcing Chains cracks it. You don't need anything more than turbot fish and xy-wing. Back to top MadOverlord Joined: 01 Jun 2005 Posts: 80 : Location: Wilmington, NC, USA Items Posted: Mon Aug 29, 2005 11:05 am    Post subject: Nick70 wrote: MadOverlord wrote: It's a toughy, but Nishio and Forcing Chains cracks it. You don't need anything more than turbot fish and xy-wing. I'm going to have to plug in some of the more esoteric variant algorithms when I get a chance. IIRC Fishy incorporates xy-wing, but not turbot. Or the other way round... Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Mon Aug 29, 2005 2:15 pm    Post subject: Nick70 wrote: You don't need anything more than turbot fish and xy-wing. I don't do either of these so my generator doesn't filter them out. Are the algorithms published somewhere. Regards Andrew Back to top rubylips Joined: 07 Apr 2005 Posts: 62 : Location: London Items Posted: Fri Sep 02, 2005 10:56 am    Post subject: Here's my pennysworth. The puzzle is straightforward to here: Code:  . . 4 | . 5 8 | 2 7 1  5 . 2 | . 1 . | 8 9 4  8 . . | 2 4 . | 3 5 6 -------+-------+------  4 8 . | 5 6 1 | . 2 .  2 9 5 | 7 3 4 | 1 6 8  . . . | 8 9 2 | . 4 . -------+-------+------  1 5 . | . 2 6 | 4 8 .  . 4 . | 1 8 . | . 3 2  . 2 8 | 4 7 . | 6 1 . whereupon my solver suggests: 23. Consider the chains (6,9)~7~(6,1)-7-(8,1)~7~(8,7) and (6,9)~7~(7,9)-7-(8,7). When the cell (6,9) contains the value 7, one chain states that the cell (8,7) contains the value 7 while the other says it doesn't - a situation that is clearly illegal. Therefore, the cell (6,9) cannot contain the value 7. - The move (6,9):=7 has been eliminated. Consider the chains (1,1)-9-(1,4)-9-(7,4)~9~(7,3) and (1,1)-9-(3,3)~9~(7,3). When the cell (7,3) contains the value 9, one chain states that the cell (1,1) contains the value 9 while the other says it doesn't - a situation that is clearly illegal. Therefore, the cell (7,3) cannot contain the value 9. - The move (7,3):=9 has been eliminated. The values 1, 6 and 9 occupy the cells (3,3), (6,3) and (8,3) in some order. - The moves (3,3):=7, (6,3):=3, (6,3):=7 and (8,3):=7 have been eliminated. The value 7 in Column 2 must lie in Box [1,1]. - The move (6,2):=7 has been eliminated. Consider the chains (4,7)~7~(4,3)-7-(7,3)-7-(7,9) and (4,7)~7~(4,9)-7-(7,9). When the cell (4,7) contains the value 7, one chain states that the cell (7,9) contains the value 7 while the other says it doesn't - a situation that is clearly illegal. Therefore, the cell (4,7) cannot contain the value 7. - The move (4,7):=7 has been eliminated. The value 9 is the only candidate for the cell (4,7). 24. Consider the chains (7,3)-3-(9,1)~9~(8,3), (7,3)-3-(9,1)~9~(8,1) and (7,3)-3-(7,4)~9~(8,6). Whichever of the 3 candidates in Row 8 contains the value 9, the cell (7,3) does not contain the value 3. - The move (7,3):=3 has been eliminated. The value 7 is the only candidate for the cell (7,3). It's straightforward after these two moves. Back to top DHallman Joined: 09 Aug 2005 Posts: 24 : Location: Inglewood, CA 90302 USA Items Posted: Fri Sep 02, 2005 8:38 pm    Post subject: [quote="rubylips"]Here's my pennysworth. The puzzle is straightforward to here: Code:  . . 4 | . 5 8 | 2 7 1  5 . 2 | . 1 . | 8 9 4  8 . . | 2 4 . | 3 5 6 -------+-------+------  4 8 . | 5 6 1 | . 2 .  2 9 5 | 7 3 4 | 1 6 8  . . . | 8 9 2 | . 4 . -------+-------+------  1 5 . | . 2 6 | 4 8 .  . 4 . | 1 8 . | . 3 2  . 2 8 | 4 7 . | 6 1 .remainder of quote] 55 done 1: Color 9's ==> excude 9 from (7,3) 2: Naked pairs c3 ==> excude 3 & 7 from remainder of c3 3: Box 1 , 7's locked ==> excude 7 from (6,2) 4: color 7's ==> excude 7 from (6,9) 5: x-wing 7 ==> excude 7 from (4,7) ==> (4,7) = 9 or 5: color 9's if G true (4,7) = 9 if B true (4,7) = 9 ==> (4,7) = 9 54 done 6: xy-wing (7,3), (7,9),(9,1) ==> exclude 9 from (9,9) ==> (9,9) = 5 Solution follows. David Back to top AW Joined: 16 Feb 2007 Posts: 2 : Items Posted: Sat Feb 17, 2007 12:06 am    Post subject: I've been making a few enhancements to this approach. ravel was kind enough to point me to this thread, so I thought I'd link back from here to the other thread, in case anyone is still interested by the subject. Look forward to others joining the discussion! Well, I can't post the URL. Here it is, somewhat broken up. If anyone would be so kind to fix it, thanks ! It's over at the sudoku forums, the topic is t=5277 Back to top dpbobelisk Joined: 27 Apr 2006 Posts: 16 : Location: Kettering,UK Items Posted: Sat Feb 17, 2007 1:19 am    Post subject: AW I think this your link: http://www.sudoku.com/forums/viewtopic.php?p=41454#41454 (but I don't see 5277 anywhere in it!) BTW Have you considered adding Braiding Analysis constraints to your Mr Solver? Now that would be challenging! Back to top AW Joined: 16 Feb 2007 Posts: 2 : Items Posted: Sat Feb 17, 2007 4:54 am    Post subject: Thanks for getting the link fixed, dpbobelisk. Mine had t=5277 instead of p=41454... but anyhow, yours goes to the right place! As for braids, they seem very interesting. Thanks for the pointer. I'll be reading up on them to see if they can be worked into Solver's mechanisms. But, in David's words, Braid Analysis will definitely "require FCCEB (full cup of coffee & empty bladder) to tackle", and a good night's rest I might add! Back to top Pat Joined: 06 Sep 2006 Posts: 128 : Items Posted: Sun Feb 25, 2007 10:54 am    Post subject: re: URLs dpbobelisk wrote: AW I think this your link: http://www.sudoku.com/forums/viewtopic.php?p=41454#41454 (but I don't see 5277 anywhere in it!) the URL for a Topic uses t= http://setbb.com/sudoku/viewtopic.php?t=126 http://sudoku.com/forums/viewtopic.php?t=5277 the URL for a specific Post uses p= ( and needs the Post-number twice ) http://setbb.com/sudoku/viewtopic.php?p=7669#7669 http://sudoku.com/forums/viewtopic.php?p=41454#41454 Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Solving sudoku All times are GMT Goto page Previous  1, 2 Page 2 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