Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Killer Swordfish example
Goto page Previous  1, 2, 3, 4  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
coconut

Joined: 13 May 2005
Posts: 12
:
Location: Oxford

Items
PostPosted: Sat May 21, 2005 6:45 am    Post subject: jacko and nishio Reply with quote

What are the formal definitions of jacko and nishio and how many problems are avaialable for these?

coconut
Back to top
View user's profile Send private message
coconut

Joined: 13 May 2005
Posts: 12
:
Location: Oxford

Items
PostPosted: Sat May 21, 2005 4:38 pm    Post subject: pattern defibitions Reply with quote

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
View user's profile Send private message
BoneHead

Joined: 03 Aug 2005
Posts: 2
:

Items
PostPosted: Wed Aug 03, 2005 3:10 am    Post subject: Squirmbag example Reply with quote

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
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Wed Aug 03, 2005 3:19 am    Post subject: Re: Squirmbag example Reply with quote

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 Very Happy.

Code:
.2.|.2.|...
.2.|...|.2.
...|...|...
---+---+---
...|...|...
...|...|...
...|...|...
---+---+---
...|...|...
...|...|...
...|.2.|.2.
Back to top
View user's profile Send private message Visit poster's website
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Wed Aug 03, 2005 3:55 am    Post subject: Reply with quote

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
View user's profile Send private message
BoneHead

Joined: 03 Aug 2005
Posts: 2
:

Items
PostPosted: Wed Aug 03, 2005 12:51 pm    Post subject: Missed swordfish Reply with quote

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
View user's profile Send private message
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Wed Aug 03, 2005 3:56 pm    Post subject: Re: Missed swordfish Reply with quote

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
View user's profile Send private message
AMcK

Joined: 07 Apr 2005
Posts: 89
:
Location: Cambridge

Items
PostPosted: Wed Aug 03, 2005 4:34 pm    Post subject: Re: Missed swordfish Reply with quote

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
View user's profile Send private message Send e-mail
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Wed Aug 03, 2005 10:36 pm    Post subject: Re: Missed swordfish Reply with quote

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
View user's profile Send private message
AMcK

Joined: 07 Apr 2005
Posts: 89
:
Location: Cambridge

Items
PostPosted: Wed Aug 03, 2005 11:16 pm    Post subject: Re: Missed swordfish Reply with quote

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
View user's profile Send private message Send e-mail
AMcK

Joined: 07 Apr 2005
Posts: 89
:
Location: Cambridge

Items
PostPosted: Thu Aug 04, 2005 12:47 pm    Post subject: Re: Missed swordfish Reply with quote

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
View user's profile Send private message Send e-mail
droid42

Joined: 29 Jul 2005
Posts: 20
:

Items
PostPosted: Thu Aug 04, 2005 1:11 pm    Post subject: Reply with quote

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
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Thu Aug 04, 2005 1:16 pm    Post subject: Re: Missed swordfish Reply with quote

AMcK wrote:
I can't see the swordfish.

Code:
...|...|...
...|...|...
...|.3.|3..
---+---+---
..3|.3.|3..
...|...|...
..3|.3.|...
---+---+---
...|...|...
...|...|...
...|...|...
Back to top
View user's profile Send private message Visit poster's website
droid42

Joined: 29 Jul 2005
Posts: 20
:

Items
PostPosted: Thu Aug 04, 2005 1:29 pm    Post subject: Re: Missed swordfish Reply with quote

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
View user's profile Send private message
AMcK

Joined: 07 Apr 2005
Posts: 89
:
Location: Cambridge

Items
PostPosted: Thu Aug 04, 2005 4:18 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Goto page Previous  1, 2, 3, 4  Next
Page 3 of 4

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron