FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Pure Jellyfish? Goto page Previous  1, 2          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Tue Aug 09, 2005 12:48 am    Post subject: First one is neat. New n-Wings algorithm finds the 4x4 instantaneously using row/column occupancy bitmaps Column n-Wing found p=1 n=3 columns 6 8 9 rows 1 3 5 Column n-Wing found p=2 n=4 columns 2 3 6 7 rows 1 2 5 9 Reduction in {3,6}: before=1278 after=178 Reduction in {8,2}: before=28 after=8 Row n-Wing found p=2 n=5 rows 3 4 6 7 8 cols 1 4 5 8 9 Column n-Wing found p=3 n=2 columns 2 8 rows 4 6 Row n-Wing found p=3 n=2 rows 4 6 cols 2 8 Column n-Wing found p=4 n=2 columns 8 9 rows 5 8 Row n-Wing found p=4 n=2 rows 5 8 cols 8 9 Column n-Wing found p=5 n=2 columns 4 9 rows 7 8 Row n-Wing found p=5 n=2 rows 7 8 cols 4 9 Column n-Wing found p=7 n=7 columns 2 3 4 5 6 7 8 rows 1 2 3 5 6 7 9 Row n-Wing found p=8 n=4 rows 2 3 7 8 cols 1 2 6 8 Column n-Wing found p=9 n=2 columns 2 5 rows 4 6 Row n-Wing found p=9 n=2 rows 4 6 cols 2 5 However, you don't need to look for the Jellyfish because after applying simple rules it can be supercoloured to completion without needing any further application of rules. Code: 9    5      2a7a ¦ 6      3      1a2b     ¦ 4    1b7b 8      3    2c7b8a 1    ¦ 4      5      2d8b     ¦ 2e7a 6    9      2f8b 4      6    ¦ 9      2g7e   1b2h7f8a ¦ 3    5    1a2i    -----------------+------------------------+------------------ 6    3a9a   4    ¦ 1      2j9b   5        ¦ 8    2k3b 7      5    2a7a   2b7b ¦ 3      8      6        ¦ 9    1a4a 1b4b    1    3b9b   8    ¦ 2n7e   2o7f9a 4        ¦ 5    2j3a 6      -----------------+------------------------+------------------ 2q8a 6      3    ¦ 2r5a7b 4      9        ¦ 1    7a8b 2s5b    7    2f8b   9    ¦ 2u5b   1      3        ¦ 6    4b8a 2v4a5a 4    1      5    ¦ 8      6      2e7a     ¦ 2i7b 9    3      Conflict: 1b implies 1a and 1b implies 2b but 1a excludes 2b Reduction: 1b=false in {5,9} before=14 after=4 Conflict: 2c implies 2f and 2c implies 2i but 2f excludes 2i Reduction: 2c=false in {2,2} before=278 after=78 Conflict: 2d implies 2f and 2d implies 2i but 2f excludes 2i Reduction: 2d=false in {2,6} before=28 after=8 Conflict: 2h implies 2i and 2h implies 8a but 2i excludes 8a Reduction: 2h=false in {3,6} before=278 after=78 Conflict: 2j implies 2k and 2j implies 3b but 2k excludes 3b Reduction: 2j=false in {6,8} before=23 after=3 Conflict: 2o implies 4a and 2o implies 8a but 4a excludes 8a Reduction: 2o=false in {6,5} before=279 after=79 Conflict: 2r implies 4a and 2r implies 8a but 4a excludes 8a Reduction: 2r=false in {7,4} before=257 after=57 Conflict: 2s implies 4a and 2s implies 5a but 4a excludes 5a Reduction: 2s=false in {7,9} before=25 after=5 Conflict: 2u implies 4a and 2u implies 5a but 4a excludes 5a Reduction: 2u=false in {8,4} before=25 after=5 Conflict: 3b implies 4a and 3b implies 8a but 4a excludes 8a Reduction: 3b=false in {6,2} before=39 after=9 Conflict: 4a implies 7a and 4a implies 8a but 7a excludes 8a Reduction: 4a=false in {8,9} before=245 after=25 Conflict: 5a implies 7a and 5a implies 8a but 7a excludes 8a Reduction: 5a=false in {8,9} before=25 after=2 Conflict: 7a implies 7e and 7a implies 8a but 7e excludes 8a Reduction: 7a=false in {7,8} before=78 after=8 Regards Andrew Back to top angusj Site Admin Joined: 18 Jun 2005 Posts: 406 : Items Posted: Tue Aug 09, 2005 12:53 am    Post subject: AMcK wrote: Conflict: 1b implies 1a and 1b implies 2b but 1a excludes 2b Andrew, doesn't 1b exclude 1a??? AMcK wrote: Conflict: 2c implies 2f and 2c implies 2i but 2f excludes 2i Similarly, doesn't 2c exclude 2f? Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Tue Aug 09, 2005 1:23 am    Post subject: angusj wrote: AMcK wrote: Conflict: 1b implies 1a and 1b implies 2b but 1a excludes 2b Andrew, doesn't 1b exclude 1a??? Yes, that looks to be the obvious assertion. However ... Code: Exclusion in {7,8} 7a excludes 8b Conjugate in row 2 8a conjugates 8b 7a excludes 8b and 8b conjugates 8a so 7a implies 8a 1b implies 7a and 7a implies 8a so 1b implies 8a Exclusion in {3,6} 1b excludes 8a Conjugate in row 1 1a conjugates 1b 8a excludes 1b and 1b conjugates 1a so 8a implies 1a 1b implies 8a and 8a implies 1a so 1b implies 1a AMcK wrote: Conflict: 2c implies 2f and 2c implies 2i but 2f excludes 2i Similarly, doesn't 2c exclude 2f? This one's a bit harder ... Code: Constraint in col 2 2c excludes 2a Conjugate in row 1 2a conjugates 2b 2c excludes 2a and 2a conjugates 2b so 2c implies 2b Exclusion in {1,6} 1a excludes 2b Conjugate in row 1 1a conjugates 1b 2b excludes 1a and 1a conjugates 1b so 2b implies 1b Exclusion in {1,8} 1b excludes 7b Conjugate in row 1 7a conjugates 7b 1b excludes 7b and 7b conjugates 7a so 1b implies 7a Exclusion in {7,8} 7a excludes 8b Conjugate in row 2 8a conjugates 8b 7a excludes 8b and 8b conjugates 8a so 7a implies 8a 1b implies 7a and 7a implies 8a so 1b implies 8a Exclusion in {7,1} 2q excludes 8a Conjugate in col 1 2f conjugates 2q 8a excludes 2q and 2q conjugates 2f so 8a implies 2f 1b implies 8a and 8a implies 2f so 1b implies 2f 2b implies 1b and 1b implies 2f so 2b implies 2f 2c implies 2b and 2b implies 2f so 2c implies 2f BTW just checked the transcript and see that it first finds lots of identities in the 2's and is able to prove: Code: Immediate certainty:   2a   row 3   {1,3}   before=27   after=2 Immediate contradiction:   2b   row 3   {1,6}   before=12   after=1 Immediate certainty:   2a   row 3   {2,7}   before=27   after=2 Immediate contradiction:   2b   row 3   {3,1}   before=28   after=8 Immediate contradiction:   2b   row 3   {3,9}   before=12   after=1 Immediate certainty:   2a   row 3   {5,2}   before=27   after=2 Immediate contradiction:   2b   row 3   {5,3}   before=27   after=7 Immediate certainty:   2a   row 3   {7,1}   before=28   after=2 Immediate contradiction:   2b   row 3   {8,2}   before=28   after=8 Immediate certainty:   2a   row 3   {9,6}   before=27   after=2 Immediate contradiction:   2b   row 3   {9,7}   before=27   after=7 I haven't followed the backtrace to see how it does this - I may have to put a little more tracing in - like the recoloured map. Regards Andrew Back to top angusj Site Admin Joined: 18 Jun 2005 Posts: 406 : Items Posted: Tue Aug 09, 2005 2:16 am    Post subject: AMcK wrote: Code: Exclusion in {7,8} 7a excludes 8b Conjugate in row 2 8a conjugates 8b 7a excludes 8b and 8b conjugates 8a so 7a implies 8a 1b implies 7a and 7a implies 8a so 1b implies 8a Exclusion in {3,6} 1b excludes 8a Isn't that sufficient to draw the conclusion that 1b is false? (ie If 1b implies 8a and 1b excludes 8a, then 1b = false.) Anyhow, that makes much more sense to me than the first explanation. ps: I'm really not trying to be critical, I'm just trying to understand what's going on. Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Tue Aug 09, 2005 4:10 am    Post subject: AMcK wrote: Column n-Wing found p=2 n=4 columns 2 3 6 7 rows 1 2 5 9 Row n-Wing found p=2 n=5 rows 3 4 6 7 8 cols 1 4 5 8 9 You'll never need n>4, because there's always a dual of smaller size, as can be seen in the above two lines: the second is the dual of the first. Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Tue Aug 09, 2005 8:23 am    Post subject: angusj wrote: Isn't that sufficient to draw the conclusion that 1b is false? (ie If 1b implies 8a and 1b excludes 8a, then 1b = false.) Anyhow, that makes much more sense to me than the first explanation. ps: I'm really not trying to be critical, I'm just trying to understand what's going on. Of course, you're right, but the supercolourer just gives us the first answer no matter its complexity. I have difficulty following some of its reasoning but thye only way I catch it out is when there's a bug. I suppose I'll have to teach it to look at all the logic chains and report the best i.e. shortest. Andrew p.s. be as critical as you like - that's what stimulates progress Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Wed Aug 10, 2005 9:50 am    Post subject: Nick70 wrote: AMcK wrote: Column n-Wing found p=2 n=4 columns 2 3 6 7 rows 1 2 5 9 Row n-Wing found p=2 n=5 rows 3 4 6 7 8 cols 1 4 5 8 9 You'll never need n>4, because there's always a dual of smaller size, as can be seen in the above two lines: the second is the dual of the first. That's very cute - so in either case the same 2 cells get zapped. Code: Reduction in {3,6}: before=1278 after=178 Reduction in {8,2}: before=28 after=8 I must try to work out a general proof. Pity about not needing 1-9 because I'd got the run time down for the entire scan to under 20 mS Andrew Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Wed Aug 10, 2005 11:41 am    Post subject: AMcK wrote: Nick70 wrote: You'll never need n>4, because there's always a dual of smaller size, as can be seen in the above two lines: the second is the dual of the first. I must try to work out a general proof. It's quite simple. If you have N rows where the number can only appear in N columns, then in the remaining 9-N columns the number can only appear in the remaining 9-N rows! Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Wed Aug 10, 2005 11:53 am    Post subject: Nick70 wrote: It's quite simple. If you have N rows where the number can only appear in N columns, then in the remaining 9-N columns the number can only appear in the remaining 9-N rows! Neat! So you could just scan for column n-wings 2-9 and forget the rows. Because my algorithm is recursive (starts with N=0, adds the next available column and calls itself with N=N+1) that would be quicker. But the emphasis right now is for the simplest, easist to understand, proof so I'll leave it at N=2-4 rows/columns. Thanks AMcK Back to top droid42 Joined: 29 Jul 2005 Posts: 20 : Items Posted: Fri Aug 12, 2005 8:13 am    Post subject: New n-Wings algorithm finds the 4x4 instantaneously using row/column occupancy bitmaps This sounds like exactly how I coded my n-Wings algorithm too. Have you spotted yet that this algorithm, virtually unchanged can also be used to reliably find naked and hidden n-tuples? Ian. Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Fri Aug 12, 2005 12:16 pm    Post subject: droid42 wrote: New n-Wings algorithm finds the 4x4 instantaneously using row/column occupancy bitmaps This sounds like exactly how I coded my n-Wings algorithm too. The row occupancy bitmap ro[(1-9, 1-9] has bit c is set if the cell [r,c] has p as a possible. The column occupancy bitmap co[1-9, 1-9] has bit r is set if the cell [r,c] has p as a possible. Each entry has 9 bits so its numerical value is 0-511. This means you can do some very neat functions by vector lookup. BitCount[0-511] counts how many bits are set i.e. how many rows/colums are occupied. BitMax[0-511] tells you the highest bit set i.e. the highest occupied row/column. The algorithm is then simply [edited error in pseudo code] Code: for poss = 1 to 9   xWings poss,0,empty next poss where recursive xWings(poss,n,cols) is Code: rows = empty for each col in cols    for each row in co(poss, col)      if co(poss,row) in cols then        rows = rows or {row}      end if    next row next col if n>2 and BitCount(rows) = n then xWing found if n<5 then "Nick70's simplification"   for col = bitMax(cols) + 1 To 8     if bitCount(co(poss, col)) > 1 Then       xWings poss,n+1,cols+{col}     end if   next col end if The yWings is the transposition or row(s) and col(s). Total time for table creation xWing and yWing typically < 16 mS. I might try to retrofit some of this into the supercolourer once the implies vs excludes debate concludes. droid42 wrote: Have you spotted yet that this algorithm, virtually unchanged can also be used to reliably find naked and hidden n-tuples? No I hadn't spotted that but I'm often amazed at how the different solution algorithms overlap. Andrew Last edited by AMcK on Fri Aug 12, 2005 2:37 pm; edited 1 time in total Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Fri Aug 12, 2005 2:34 pm    Post subject: AMcK wrote: I might try to retrofit some of this into the supercolourer once the implies vs excludes debate concludes. Has it started? Back to top Scott H Joined: 29 Jul 2005 Posts: 2 : Location: Oregon, USA Items Posted: Mon Aug 15, 2005 4:42 am    Post subject: Re: Pure Jellyfish? Nick70 wrote: Anyway, guess what? Since I rearranged the difficulty rating in my solver, two problems that previously qualified as "xy-wing" (because xy-wing was rated more difficult than quadruples), now qualify as "jellyfish"! Code: ..2.8.7.4 .396..... 6........ .....5... ..8.1.9.. ...4..... ........6 .....782. 7.4.9.3.. ..2.8.5.6 .396..... 7........ .....5... ..8.1.9.. ...4..... ........7 .....782. 5.6.9.3.. I find an "xyz-wing" in both of these that solve the puzzle, but I don't find any xy-wings. Am I missing something? Thanks. BTW, I really like your xy-wing compendium. Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Mon Aug 15, 2005 7:29 am    Post subject: Re: Pure Jellyfish? Scott H wrote: I find an "xyz-wing" in both of these that solve the puzzle, but I don't find any xy-wings. I think the xyz-wing you found replaces the Jellyfish + xy-wing that I had found. Which one of the two solutions should be considered "simpler" is debatable, both jellyfish and xyz-wing are pretty advanced techniques. 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