FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Killer Swordfish example Goto page Previous  1, 2, 3, 4  Next          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message coconut Joined: 13 May 2005 Posts: 12 : Location: Oxford Items Posted: Sat May 21, 2005 6:45 am    Post subject: jacko and nishio What are the formal definitions of jacko and nishio and how many problems are avaialable for these? coconut Back to top coconut Joined: 13 May 2005 Posts: 12 : Location: Oxford Items Posted: Sat May 21, 2005 4:38 pm    Post subject: pattern defibitions Further to my previous messages, the formal definitions for xwing, swordfish, jacko, nishio etc etc should be enshrined in the library section. Otherwise, it is not always easy to follow the discussions. coconut Back to top BoneHead Joined: 03 Aug 2005 Posts: 2 : Items Posted: Wed Aug 03, 2005 3:10 am    Post subject: Squirmbag example A while back: coconut wrote: Are there problems which can be solved only via jellyfish or squirmbag (without nishio, of course) ? coconut I recently came encountered a puzzle that I could only solve by finding a Squirmbag. Now, I'm just a humble pencil-and-paper Sudoku addict, so it is very possible I missed an easier technique. I'm hoping that one of you guys with a clever solver (or good with pencil and paper) can point out the easier step for me. If no one can find one, maybe this is an example of a puzzle needing a Squirmbag. The original: 6 * 7 3 * 8 5 * 4 5 * * 4 * 6 * * 9 * * * * 1 * * * * 9 6 * * * * * 4 8 * * 4 * 6 * 1 * * 7 1 * * * * * 9 6 * * * * 3 * * * * 4 * * 5 * 7 * * 1 3 * 6 1 * 4 9 * 7 Using standard reduction techniques, and one X-wing to eliminate 9 as a candidate in box 3 of row 8, I was left with: 6 * 7 3 * 8 5 1 4 5 * 1 4 7 6 8 * 9 * 4 * * 1 5 * * * 9 6 * * 5 1 * 4 8 * * 4 * 6 * 1 * * 7 1 5 8 4 * * 9 6 1 7 * 6 3 * * * * 4 * * 5 * 7 * * 1 3 5 6 1 * 4 9 * 7 At which point, the only way I could finish was by finding a Squirmbag in the 2's. Can someone show me the simpler technique that I must have missed? If not, here's the squirmbag: The candidates for 2's are currently: . 2 . . 2 . . . . . 2 . . . . . 2 . 2 . 2 2 . . . . 2 . . 2 2 . . 2 . . 2 2 . 2 . 2 . . . . . . . . 2 2 . . . . 2 . . 2 . 2 2 . 2 2 . 2 . . . . . . . . 2 . . 2 . Notice that there are five columns (column #'s 1, 4, 6, 7, and 9) that contain the candidate 2 in only one of five rows (row #'s 3, 4, 5, 6, and 7). These cells must account for any possible 2's in those rows (the generalization of the X-wing principle, for N = 5 rows and columns). That means we can eliminate 2 as a candidate in rows 3 through 7 for all the other columns. That is: . 2 . . 2 . . . . . 2 . . . . . 2 . 2 . X 2 . . . . 2 . . X 2 . . 2 . . 2 X . 2 . 2 . . . . . . . . 2 2 . . . . X . . 2 . X 2 . 2 2 . 2 . . . . . . . . 2 . . 2 . From there the entire puzzle is solveable. I appologize in advance if I mistyped any of the grids above, it is getting late for me. -- BoneHead Back to top angusj Site Admin Joined: 18 Jun 2005 Posts: 406 : Items Posted: Wed Aug 03, 2005 3:19 am    Post subject: Re: Squirmbag example BoneHead wrote: I recently came encountered a puzzle that I could only solve by finding a Squirmbag. Hi Bonehead. You appear to have missed the swordfish in those 2s . Code: .2.|.2.|... .2.|...|.2. ...|...|... ---+---+--- ...|...|... ...|...|... ...|...|... ---+---+--- ...|...|... ...|...|... ...|.2.|.2. Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Wed Aug 03, 2005 3:55 am    Post subject: A Squirmbag (which has size 5) will always be the dual of a lesser pattern (from 4 downwards). So the most you can expect to need is Jellyfish. I still haven't found a "pure" Jellyfish, however--I've found a few problems where it could be used to move forward but the puzzle required more advanced techniques to be finished. P.S. Of course I'm considering the patterns in their broadest assumption, where e.g. a Swordfish can have up to 3 cells per line, not just 2 as it was initially defined. Back to top BoneHead Joined: 03 Aug 2005 Posts: 2 : Items Posted: Wed Aug 03, 2005 12:51 pm    Post subject: Missed swordfish AJ -- Thanks. I knew it had to be something simple that my eyes or brain just overlooked. I suspect that the reason no one can find a pure Jellyfish or Squirmbag example is that any higher-order elimination can be expressed as the combination of two or more X-wing (N=2) or Swordfish (N=3) patterns. If anyone out there is versed in the mathematics of number theory, I would be interested in seeing a rigorous proof of that (maybe someone can point me to a forum where these types of proofs are discussed, if one exists?) -- BH Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Wed Aug 03, 2005 3:56 pm    Post subject: Re: Missed swordfish BoneHead wrote: I would be interested in seeing a rigorous proof of that I'm afraid there cannot be, because it just isn't true. I have found some puzzles containing a Jellyfish at some point, but they were so hard that after that they would require higher techniques anyway to be solved, so I don't have a "pure" Jellyfish example yet. Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Wed Aug 03, 2005 4:34 pm    Post subject: Re: Missed swordfish Nick70 wrote: I have found some puzzles containing a Jellyfish at some point, but they were so hard that after that they would require higher techniques anyway to be solved, so I don't have a "pure" Jellyfish example yet. Nick, are we agreed that some variant of colouring can solve any fishy conjugate problem for abritrary values of N. All the fishy conjugates use a single possible but I did hear someone claim that simple colouring was not sufficient for N>3. I've not seen any fishy puzzle that defeated supercolouring. Andrew Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Wed Aug 03, 2005 10:36 pm    Post subject: Re: Missed swordfish AMcK wrote: Nick, are we agreed that some variant of colouring can solve any fishy conjugate problem for abritrary values of N. All the fishy conjugates use a single possible but I did hear someone claim that simple colouring was not sufficient for N>3. I've not seen any fishy puzzle that defeated supercolouring. Try this one Code: ..1.9.4.5 .326..... 5........ .....5... ..6.1.8.. ...4..... ........3 .....762. 8.9.4.7.. Coloring cannot work out a swordfish unless there are only two cells in each row/col of the pattern. In the more general pattern consisting of up to 9 cells there are no conjugates that can let coloring work it out. Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Wed Aug 03, 2005 11:16 pm    Post subject: Re: Missed swordfish Nick70 wrote: Coloring cannot work out a swordfish unless there are only two cells in each row/col of the pattern. In the more general pattern consisting of up to 9 cells there are no conjugates that can let coloring work it out. Agreed, supercolouring is unable to solve this. Some deep thought required. Andrew Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Thu Aug 04, 2005 12:47 pm    Post subject: Re: Missed swordfish Nick70 wrote: Try this one Code: ..1.9.4.5 .326..... 5........ .....5... ..6.1.8.. ...4..... ........3 .....762. 8.9.4.7.. Sorry, you're going to have to help me with this one Nick. I can't see the swordfish. know that a brute force guess of {1,1}=7 is sufficient to enable the solution but I can't see how to prove it. Andrew Back to top droid42 Joined: 29 Jul 2005 Posts: 20 : Items Posted: Thu Aug 04, 2005 1:11 pm    Post subject: coconut wrote: Are there problems which can be solved only via jellyfish or squirmbag (without nishio, of course) ? coconut Not sure about "pure jellyfish or squirmbag" but, according to my solver, this one can only be solved with jellyfish followed by super-colouring, i.e. super-colouring alone isn't enough (I already posted this on the super-colouring thread). My solver doesn't do forced-chains (yet) ot Nishio (I refuse to build any t/e logic into it for the moment) so any other opinions on it gratefully received... Ian. Code: 52.....7. .......4. .3.47...6 .1368.... ...39.... 64......3 ....4.7.. .68..5..1 47.....2. Back to top angusj Site Admin Joined: 18 Jun 2005 Posts: 406 : Items Posted: Thu Aug 04, 2005 1:16 pm    Post subject: Re: Missed swordfish AMcK wrote: I can't see the swordfish. Code: ...|...|... ...|...|... ...|.3.|3.. ---+---+--- ..3|.3.|3.. ...|...|... ..3|.3.|... ---+---+--- ...|...|... ...|...|... ...|...|... Back to top droid42 Joined: 29 Jul 2005 Posts: 20 : Items Posted: Thu Aug 04, 2005 1:29 pm    Post subject: Re: Missed swordfish AMcK wrote: Nick70 wrote: Try this one Code: ..1.9.4.5 .326..... 5........ .....5... ..6.1.8.. ...4..... ........3 .....762. 8.9.4.7.. Sorry, you're going to have to help me with this one Nick. I can't see the swordfish. know that a brute force guess of {1,1}=7 is sufficient to enable the solution but I can't see how to prove it. Andrew My solver says that the "simplest" (not necessarily the quickest) way to solve this one is as follows (I've abbreviated the log heavily...) Code: {2,5}=5 {9,9}=1 {9,8}=5 {7,7}=9 {2,7}=1 {5,2}=5 {6,7}=5 {8,4}=9 {8,3}=5 {7,4}=5 {7,6}=1 {3,4}=1 {8,1}=3 {8,2}=1 {8,5}=8 {8,9}=4 {7,8}=8 Simple Logic: 17 cells solved in 4 passes {3,5}!2 {3,6}!2 [Pointing pair value=2 box=3 row=3] {4,4}!3 {3,6}!3 {6,6}!3 {3,8}!3 {4,8}!3 {6,8}!3 [Swordfish(3) value=3 rows 1,5,9] {1,4}!8 {1,6}!8 [Solitary pair box 2 values=4,8] {6,6}!8 [Solitary pair column 6 values=4,8] {1,2}=8  {4,4}=8  {6,3}=8 {4,3}=3 {6,5}=3 {4,7}=2 {5,8}=3  {4,8}=44  {6,8}=1 {3,7}=3 {3,9}=2 {2,9}=8 {4,1}=1  {2,6}=4 {3,5}=7 {3,6}=8 {3,3}=4 {7,3}=7 {4,5}=6 {5,4}=7 {5,1}=4 {5,6}=2 {5,9}=9 {7,5}=2 {6,6}=9 {6,9}=6 {1,6}=3 {9,6}=6 {4,9}=7 {7,1}=6 {7,2}=4 {9,2}=2 {9,4}=3 {1,1}=7 {1,4}=2  {1,8}=6  {2,1}=9 {6,1}=2 {3,2}=6 {2,8}=7 {4,2}=9 {6,2}=7 {3,8}=9 Simple Logic: 43 cells solved in 4 passes Ian. Back to top AMcK Joined: 07 Apr 2005 Posts: 89 : Location: Cambridge Items Posted: Thu Aug 04, 2005 4:18 pm    Post subject: Thanks to you both for assistance. I see that my "simple logic" pre-solver had missed the N=2 pair in column 6 and I was colouring from {3,6}=348 rather than your 48. Theimplementation of my intended rule appears also correct so I need to go away and look at this carefully to see if I've confused two similar rules. Meanwhile, if I lose the 3, the colour map becomes: Code: 6a7a       6b7b8a     1        2a3a7c8b 9        2b3b8c     4    3c6c7d       5          4a7e9a     3          2        6        5        4b8d       1    7f9b         7g8e9c      5          4c6d7h8f9d 4d7i8g   1        3d7j     4a8h       2c3e 3f6e7k9e     2d6f7l8d9f 1a2e4f7m9g 2f4g7n8j9h 3g4h7o8k 2g3h7p8l 2h3i6g7q 5          2d3j 1b3k4i6h7r9i 2j6i7s9j    2k4i7t9k   5          6        2l3l7u   1        2m3m9l     8    3n4k7v9m     2n7w9n      1b2o7x9o   2p7y8m9p   3o7z8n   4        2q3p6j7A 2r3q6k8b9q 5    1a3r6l7B9r   2s6m7C9s    2t4l6n7D   2u4m6o7E   4n7F     5        2v6k     1          9    8            3          3          1          5        9        8        7          6    2            4          8          2w6k       9        2x3s     4        2y3t6r     7    5            1          Super-colouring then is able to discover: Code: Exclusion in {4,4} 3h excludes 8l Conjugate in col 4 8b conjugates 8l 3h excludes 8l and 8l conjugates 8b so 3h implies 8b Exclusion in {6,6} 6k excludes 8b Conjugate in row 9 6k conjugates 6r 8b excludes 6k and 6k conjugates 6r so 8b implies 6r 3h implies 8b and 8b implies 6r so 3h implies 6r Exclusion in {9,6} 3t excludes 6r Conjugate in row 9 3s conjugates 3t 6r excludes 3t and 3t conjugates 3s so 6r implies 3s 3h implies 6r and 6r implies 3s so 3h implies 3s Constraint in col 4 3h excludes 3s Conjugate in row 9 3s conjugates 3t 3h excludes 3s and 3s conjugates 3t so 3h implies 3t Constraint in row 9 3s excludes 3t Conflict: 3h implies 3s and 3h implies 3t but 3s excludes 3t Reduction: 3h=false in {4,4} before=2378 after=278 It's only one reduction but that's enough to solve the rest by "simple logic". So apologies for the error - but I'm still looking for a logically solvable puzzles that supercolouring can't solve. Andrew 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, 3, 4  Next Page 3 of 4   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