Sudoku Programmers :: View topic

FAQ

Memberlist

Usergroups

Profile

Pure Jellyfish?
Goto page 1, 2 Next

Sudoku Programmers Forum Index -> Solving sudoku

View previous topic :: View next topic

Author

Message

droid42

Joined: 29 Jul 2005

Posts: 20

Items

Posted: Sun Aug 07, 2005 12:32 am Post subject: Pure Jellyfish?

In response to a question in a previous thread, I've been trying to generate a 9x9 puzzle requiring a jellyfish-solve to get any further (ignoring super-colouring which is waaaaay too effective to be considered conventional logic Wink

).

Here are a couple of candidates. Would like some second opinions as to whether I've succeeded or not (I'm still not 100% happy with my solver's assessments of some situations).

Ian.

Code:

.5......8
..145...9
...9..35.
..4...8.7
...3.6...
1.8...5..
.63..9...
7...136..
4......9.

Code:

..5...2..
32...6...
.4..8..1.
51.26...8
..9.5.4..
2...49.51
.8..7..2.
...3...64
..3...5..

angusj
Site Admin

Joined: 18 Jun 2005

Posts: 406

Items

Posted: Sun Aug 07, 2005 2:26 am Post subject: Re: Pure Jellyfish?

droid42 wrote:

Here are a couple of candidates. Would like some second opinions as to whether I've succeeded or not.

The first one looks very good to me Very Happy

...

Code:

..2|..2|...
.2.|..2|2..
...|...|...
---+---+---
...|...|...
.22|...|...
...|...|...
---+---+---
...|...|...
...|...|...
...|..2|2..

However, the second one only needs a Swordfish.

droid42

Joined: 29 Jul 2005

Posts: 20

Items

Posted: Sun Aug 07, 2005 6:34 am Post subject: Re: Pure Jellyfish?

angusj wrote:

droid42 wrote:

Here are a couple of candidates. Would like some second opinions as to whether I've succeeded or not.

The first one looks very good to me Very Happy

...

Code:

..2|..2|...
.2.|..2|2..
...|...|...
---+---+---
...|...|...
.22|...|...
...|...|...
---+---+---
...|...|...
...|...|...
...|..2|2..

However, the second one only needs a Swordfish.

Ah excellent ... on two counts.

1. The jellyfish you found matches the one that my post-generator report says
2. Your analysis of the second one also agrees with my program ... this will teach me to wear my glasses in future and not mistake "sf" for "bf" again ...

Thanks for checking that out. I have plenty more which I'll probably post later...

Ian.

Nick70

Joined: 08 Jun 2005

Posts: 160

Items

Posted: Sun Aug 07, 2005 8:30 am Post subject: Re: Pure Jellyfish?

droid42 wrote:

Here are a couple of candidates. Would like some second opinions as to whether I've succeeded or not

The first one is almost there, but it can be solved with a simple XY-Wing. If you disable XY-Wing then you need a Jellyfish.

Code:

9 5 27 | 6 3 12 | 4 17 8
3 278 1 | 4 5 28 | 27 6 9
28 4 6 | 9 27 178 | 3 5 12
-------------------+--------------------+-------------------
6 39 4 | 1 29 5 | 8 23 7
5 27 27 | 3 8 6 | 9 14 14
1 39 8 | 27 279 4 | 5 23 6
-------------------+--------------------+-------------------
28 6 3 | 257 4 9 | 1 78 25
7 28 9 | 25 1 3 | 6 48 245
4 1 5 | 8 6 27 | 27 9 3
Found a xy-wing: r1c6 <-- r1c8 --> r2c7
- Remove 2 from r2c6

angusj
Site Admin

Joined: 18 Jun 2005

Posts: 406

Items

Posted: Sun Aug 07, 2005 8:58 am Post subject: Re: Pure Jellyfish?

Nick70 wrote:

Found a xy-wing: r1c6 <-- r1c8 --> r2c7

There's another one too:
r1c3 <--> r1c8 <--> r3c9 ==> exclude 2 from r3c1.

Nick70

Joined: 08 Jun 2005

Posts: 160

Items

Posted: Sun Aug 07, 2005 9:33 am Post subject: Re: Pure Jellyfish?

angusj wrote:

There's another one too:
r1c3 <--> r1c8 <--> r3c9 ==> exclude 2 from r3c1.

Right. My program preferred the other one because it has three straight sides.

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

droid42

Joined: 29 Jul 2005

Posts: 20

Items

Posted: Sun Aug 07, 2005 11:12 am Post subject: Re: Pure Jellyfish?

Nick70 wrote:

droid42 wrote:

Here are a couple of candidates. Would like some second opinions as to whether I've succeeded or not

The first one is almost there, but it can be solved with a simple XY-Wing. If you disable XY-Wing then you need a Jellyfish.

Code:

Interesting. I'd previously avoided coding XY-wing because I assumed (perhaps incorrectly?) that super-colouring is a superset of it ...

How about the following...?

Code:

...8..6..
46.7....1
.7...1.48
......3.2
....2....
8.5......
35.4...6.
6....3.89
..7..9...

This one also appears to have a naked quad followed by a jellyfish... (don't know about XY-Wing though)

Ian.

angusj
Site Admin

Joined: 18 Jun 2005

Posts: 406

Items

Posted: Sun Aug 07, 2005 11:29 am Post subject: Re: Pure Jellyfish?

droid42 wrote:

This one also appears to have a naked quad followed by a jellyfish...

No, after the naked quad it's plain sailing. Certainly no jellyfish required.

droid42

Joined: 29 Jul 2005

Posts: 20

Items

Posted: Sun Aug 07, 2005 12:15 pm Post subject: Re: Pure Jellyfish?

angusj wrote:

droid42 wrote:

This one also appears to have a naked quad followed by a jellyfish...

No, after the naked quad it's plain sailing. Certainly no jellyfish required.

Oh, that's odd.

After the naked quad I get the following position...

Code:

1259 139 123 (8) 3459 245 (6) (7) 35
(4) (6) (8) (7) 359 25 259 23 (1)
259 (7) 23 23569 3569 (1) 259 (4) (8)
179 149 146 159 48 4678 (3) 159 (2)
179 1349 1346 159 (2) 467 (8) 159 46
(8) (2) (5) 139 139 46 (7) 19 46
(3) (5) (9) (4) 18 28 12 (6) (7)
(6) 14 124 125 (7) (3) 125 (8) (9)
12 (8) (7) 1256 156 (9) (4) 23 35

And (using logic alone) my solver won't get any further without super-colouring or jellyfish (and neither can I but I put that down to a night on the town and 3 hours sleep last night Wink

) NB: My solver doesn't yet incorporate XY-Wing or Forcing Chains so is that perhaps why?

Ian.

angusj
Site Admin

Joined: 18 Jun 2005

Posts: 406

Items

Posted: Sun Aug 07, 2005 1:08 pm Post subject: Re: Pure Jellyfish?

droid42 wrote:

After the naked quad I get the following position...

Look at box 5 (the middle one) and filter on 5s.
You'll see that there are 5's only in the left most column (col 4) in that box and since one of them must be the 5, 5s can be excluded from the rest of column 4 outside box 5. (See also http://www.angusj.com/sudoku/hints.php#locked_candidates_1)

droid42

Joined: 29 Jul 2005

Posts: 20

Items

Posted: Sun Aug 07, 2005 1:36 pm Post subject: Re: Pure Jellyfish?

angusj wrote:

droid42 wrote:

After the naked quad I get the following position...

Yep, trivial box/line reduction which my solver spots if I feed that final position into it from scratch but seems to miss if I start with the original grid. Hmm....

Ian.

RichardP

Joined: 08 Aug 2005

Posts: 3

Items

Posted: Mon Aug 08, 2005 11:58 am Post subject: Re: Pure Jellyfish?

angusj wrote:

The first one looks very good to me Very Happy

...

Code:

..2|..2|...
.2.|..2|2..
...|...|...
---+---+---
...|...|...
.22|...|...
...|...|...
---+---+---
...|...|...
...|...|...
...|..2|2..

Hi, I'm new to all this, so please feel free to shoot me down in flames - I'm just trying to get my head round the 'generalised x-wing' stuff.

From the look of the above grid I don't see how that is a jellyfish. The definition of a jellyfish from Daily Sudoku is

Quote:

Look for N columns (2 for X-Wing, 3 for the Swordfish, 4 for a Jellyfish, 5 for a Squirmbag) with only two candidate cells for a given value.
If these fall on exactly N common rows, and each of those rows has at least 2 candidate cells, then all N rows can be cleared of that value (except in the defining cells!).

Likewise for N rows with N common columns.

So for a jelyfish you need 4 columns on 4 rows (or 4 rows on 4 columns) which have only two cells for a given candidate, the above does not have that, there are three 2's in row 2 and three 2's in column 6.

Also (and this is probably down to my crappy solving capability!) when I solve up to this point I get possible 2's in row 8 cols 2,4 and 9, which thus should also be included, I get a grid like this:

Code:

9 5 27 ¦ 6 3 127 ¦ 4 17 8
3 278 1 ¦ 4 5 278 ¦ 27 6 9
28 4 6 ¦ 9 27 1278 ¦ 3 5 12
---------------+----------------+----------------
6 39 4 ¦ 1 29 5 ¦ 8 23 7
5 27 27 ¦ 3 8 6 ¦ 9 14 14
1 39 8 ¦ 27 279 4 ¦ 5 23 6
---------------+----------------+----------------
28 6 3 ¦ 257 4 9 ¦ 1 78 25
7 28 9 ¦ 25 1 3 ¦ 6 48 245
4 1 5 ¦ 8 6 27 ¦ 27 9 3

So please help me understand this by :

a) How are the 2's in row 8 excluded (specifically the one in (2,8))?
b) Why is this still a jellyfish when there are three candidate cells (assuming removing the 2's from row 8) for either rows or columns?

Thanks,

Richard

angusj
Site Admin

Joined: 18 Jun 2005

Posts: 406

Items

Posted: Mon Aug 08, 2005 12:18 pm Post subject: Re: Pure Jellyfish?

RichardP wrote:

So please help me understand this by :
a) How are the 2's in row 8 excluded (specifically the one in (2,8))?
b) Why is this still a jellyfish when there are three candidate cells (assuming removing the 2's from row 8) for either rows or columns?

Answering b) first: The definition of a Jellyfish you've seen is incomplete. There can be up to four candidates (not two) sharing 4 columns in 4 rows to make a Jellyfish. Likewise, there can be up to four candidates sharing 4 rows in 4 columns to make a Jellyfish.
In the case in question there are - two 2s in col1, three twos in col2, two 2s in col5 & two 2s in col 9 sharing columns 2,3,6 &7 - making a jellyfish. (Here's my definition of a Swordfish which may help you understand the general principles). Because candidate 2 in r8c2 intrudes into the Jellyfish grid it can be excluded.
Answering a): I presume you mean r8c2, not 2,8 since you did say "row 8". Anyhow, answered in b) above Smile

RichardP

Joined: 08 Aug 2005

Posts: 3

Items

Posted: Mon Aug 08, 2005 12:55 pm Post subject: Re: Pure Jellyfish?

angusj wrote:

Ah, thanks, now I think I've got that part, the rows may contain candidate cells up to the number of rows/columns, not just pairs. Obviously they have to be at least pairs, because if there was only one value it would have been assigned to its cell in the early stages.

angusj wrote:

Because candidate 2 in r8c2 intrudes into the Jellyfish grid it can be excluded.

Could you expand on this a bit more, I'm not sure why this only 'intrudes' and is not included in the jellyfish pattern. Row 8 has 3 cells that contain a 2 as a candidate, with Col 2, row 8 being a column that has others in the jellyfish pattern (assuming that this is a 'Row' jellyfish as almost every column has 2 or more candidates for 2's).

angusj wrote:

Answering a): I presume you mean r8c2, not 2,8 since you did say "row 8". Anyhow, answered in b) above Smile

Sorry, yes, I specified column then row, I should have been more specific.

RichardP

Joined: 08 Aug 2005

Posts: 3

Items

Posted: Mon Aug 08, 2005 3:41 pm Post subject: Re: Pure Jellyfish?

RichardP wrote:

angusj wrote:

Because candidate 2 in r8c2 intrudes into the Jellyfish grid it can be excluded.

Ah, I think I see where I've misunderstood. Just because a row has a candidate in a common row/column does not mean that it MUST be included in the set, just that it CAN be. If there is a set of 4 (for a Jellyfish) rows with 4 shared columns then even if there is another row which shares the column then this is not included in the set. Sorry for being dense, thanks for your explination!

Display posts from previous:

	Sudoku Programmers Forum Index -> Solving sudoku	All times are GMT Goto page 1, 2 Next
Page 1 of 2

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