Jigsaw Killer

For fans of Killer Sudoku, Samurai Sudoku and other variants

Jigsaw Killer

Postby Ruud » Tue May 02, 2006 1:39 pm

I'm not sure whether this variation does already exist, but here is a jigsaw killer that PeteTy and I created:

Image

It's not too difficult, but tricky because of all the irregular shapes crossing each other.

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby tarek » Tue May 02, 2006 4:04 pm

Nice one Ruud,

With these variants around, I would think that the best one would be A killer sudoku with the cages taking on a Toridal pattern.

Or A toridal Killer sudoku with 9 Square cages.........

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby HATMAN » Thu May 04, 2006 3:58 pm

Ruud

"not too difficult" - a slight understatement - seeing the interactions between the shapes is driving me mad. This is not a request for help as I will probably get there eventually.

In order to put your classification system into perspective how would you classify my DG KiMo 6

HATMAN
HATMAN
 
Posts: 203
Joined: 25 February 2006

Postby HATMAN » Mon May 08, 2006 2:37 pm

Ruud

Appologies about my previoius comment on your classification of the puzzle. I had made a simple arithmetic error early on which got me in a complete tangle.

Once I spotted my error it was, as you said, "not too difficult" apart from the visual problem of identifiying the cages.

Hatman
HATMAN
 
Posts: 203
Joined: 25 February 2006

Postby Ruud » Mon May 08, 2006 10:52 pm

Hi Hatman,

glad to hear that puzzle worked out fine for you.

I just created a new jigsaw killer. It has a unique solution according to the dancing links solver I implemented in SumoCue, but it exceeds the human-style solving techniques I built into the program.

How would you rate the difficulty of this jigsaw killer? The symmetry is both in the nonets and in the cages.

Image

cheers, Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby Pyrrhon » Tue May 09, 2006 8:34 am

I also like this solver, but it seems that it could increase it's power if at least two techniques would be added which are very simple to spot for a human.

The first: if I have a cage of say sum 9 and to cells with the possibilities

123678
and
2345678

Then SumoCue will not see anything, but as a human I see that at least one value can be deleted because there is a different number of values. And I can check it easy:

I go through the values of both cells and take the difference between 9 and the values. If this difference is not in the other cell we can delete the first cell.

By that we get

12367
and
23678

3 values can be deleted in this example. Because this case is very often, it is an importent technique.

The second is in the area of the 45 rule. You have it for 1 number but it is easy and powerful to consider it also for 2 numbers.

If in a house are exactly 2 cells with a cage that is not completely in the considered house than the sum of these both cells must be the same as the difference of 45 and the sum of the cages which are completely in that house. This works mostly with boxes.There is a generalistion of course but with two values it is easy to spot for an human. And it is powerful because sums of 2 values are very powerful in killer sudoku.

To check this you can use for example the following killer sudoku (SumoCue can't solve it yet). Then in the nonet 2, 7, and 9 this rule could be used.

.-----.--.-----.-----.-----.
|9 |36|23 |13 |3 |
| .--' | |-----+--.--:
| | | |7 |16|18|
:--' |-----'--.--: | |
| |16 |9 | | |
:-----.--+--.-----: | | |
|3 |14|7 |18 | | | |
:--.--: | | |--'--'--:
|15|9 | | | |22 |
| | |--'--+--.--+--------:
| | |23 |12|17|8 |
:--+--: | | |--------:
|15|20| | | |11 |
| | |-----+--+--'--.-----:
| | |9 |8 |20 |13 |
| | '--.--' | |-----:
| | | | |11 |
'--'-----'-----'-----'-----'

PS: I would like an undo-function like in SudoCue and I guess it is easy to add product sudoku and jigsaw product sudoku (and eventually frame sudoku) to this tool.
Last edited by Pyrrhon on Tue May 09, 2006 8:42 am, edited 1 time in total.
Pyrrhon
 
Posts: 240
Joined: 26 April 2006

Postby Ruud » Tue May 09, 2006 11:01 am

Thanks for the suggestions Pyrrhon,

here is your posted puzzle in code tags:
Code: Select all
.-----.--.-----.-----.-----.
|9    |36|23   |13   |3    |
|  .--'  |     |-----+--.--:
|  |     |     |7    |16|18|
:--'     |-----'--.--:  |  |
|        |16      |9 |  |  |
:-----.--+--.-----:  |  |  |
|3    |14|7 |18   |  |  |  |
:--.--:  |  |     |--'--'--:
|15|9 |  |  |     |22      |
|  |  |--'--+--.--+--------:
|  |  |23   |12|17|8       |
:--+--:     |  |  |--------:
|15|20|     |  |  |11      |
|  |  |-----+--+--'--.-----:
|  |  |9    |8 |20   |13   |
|  |  '--.--'  |     |-----:
|  |     |     |     |11   |
'--'-----'-----'-----'-----'

I am already improving the program. It is stuck on this puzzle because it does not detect a naked pair {12} in column 1. This will be fixed.

By the way, I did not find a Jigsaw Killer yet on your variants page. Feel free to use my puzzle as a sample.

cheers, Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby Pyrrhon » Wed May 10, 2006 1:28 pm

I have developed an own jigsaw killer and I know by a SumoCue dance that there is only one solution, but I can't see the next step in this situation

Image

By the way, your new version seems not to find all naked sets. In the shown jigsaw killer a naked triple in the (7,3) area in the first nonet is not used to delete the others.

And also the House-Cage-Interaction seems not to work, at least not everytime, i. e., if a digit
is in a house only in one cage then the other cells in this cage can't have this digit. Moreover this digit must occure in this cage and you can exclude eventually some other digits.

(You can see this in the picture with digit 3 in the second line and the 30(6) cage)

I have updated the killer sudoku in my collection. SumoCue can't solve the new one without a dance. One new step would be possible with 45 and the cells on the border of box 8 and 9.
Last edited by Pyrrhon on Wed May 10, 2006 12:28 pm, edited 1 time in total.
Pyrrhon
 
Posts: 240
Joined: 26 April 2006

Postby Ruud » Wed May 10, 2006 4:26 pm

Pyrrhon wrote:I have developed an own jigsaw killer and I know by a SumoCue dance that there is only one solution, but I can't see the next step in this situation

Nice Jigsaw Killer!:D I'm not sure how it can be solved without guessing. I've fixed the Jigsaw nonet omissions in the solver, but that only gives me the expected extra reductions, but no breakthrough.

You can see this in the picture with the second line and the 30(6) cage

I cannot see this in the picture. What digit should be locked in the cage?

I have updated the killer sudoku in my collection. SumoCue can't solve the new one without a dance. One new step would be possible with 45 and the cells on the border of box 8 and 9.

That is a deadly killer. I have to discount a locked pair to isolate those 2 outties. Such a trick is not yet implemented in the solver. That seems to be the only bottleneck. When I do these 2 outties manually, SumoCue can solve the rest of the puzzle. Great example.

The next version will also allow thicker borders:

Image

Thanks for your contributions. I will soon put the new version online.

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby Pyrrhon » Wed May 10, 2006 4:49 pm

Sorry my mistake, I saw the border on the false place.

But I've found a way to solve the jigsaw killer now, no guessing necessary. I'will put the puzzle on my page tomorrow.

If I'm right there are only 3 techniques which would be necessary to be implemented into SumoCue so that this program can solve this problem too (besides the naked triples in a nonet).

The first one is something around the 79 pair in R8C7 and R9C7 that allows to delete the digits 7 and 9 in R8C4, R8C5, and R8 C6. The rule is: If you have a strong link between two cells than the digit of this link can't be in any other cell which both can see. This rule is useless but valid in classical sudoku. It is very powerful in many sudoku variants (i. e., jigsaw sudoku, diagonal sudoku, disjoint group sudoku, sudokus with extragroups, isosudoku ...) Note: 2 cells in a cage can always see each other with respect to the strong link approach, they are buddies even if they don't share a column, row or nonet, but most frequently they form no strong link (But see the digit 1 in 8(3) cages). The property to be buddies is the property that leads to extra fishs which you can't catch in classical sudoku: turbot killer fishs, killer x-wings, killer swordfishs, killer variants of chains and cycles ... In our case we have a fish with only one strong link, we could call it a sickleback, but it is here no killer sickleback but a jigsaw sickleback.

The second one is something what could be called Cages-House-Difference:

For every house (nonet, row, column) look for the smallest set of cages that contains the house. If the cardinality of the difference of both sets is less than four calculate the difference of the values and use this as sum of the difference set. You would get for example R1C3+R4C2+R4C4 = 8 or R2C6 + R3C9 + R4C6 = 22 or R2C6 + R3C5 = 10.

This technique could also be used for pairs, triples ... of (neighbored) disjoint houses.

The third could be called House-Cages-Difference;

For every house (row, column, nonet), pair, triple ... of (neighbored) disjoint houses, look for all cages which are fully in that set. If the cardinality of the difference of both sets is less than four calculate the difference of the values and use this as sum of the difference set.

You would get for exemple R4C2+R7C5+R9C7 = 12 or R1C1+R2C1+R7C1 = 17.

In my normal killer you would get for the Cages-House-Difference-Technique:

R4C7+R4C8+R4C9 = 15 (2 boxes or 3 lines)
R6C4+R7C4+R8C4=18 (2 boxes)

House-Cages-Difference:

R4C7+R4C8+R4C9=15
R8C7+R9C7=10
R6C3=4
R6C3+R7C3+R8C3=14 (2 boxes)
R6C1+R6C2=13 (3 boxes and 1 line or 4 lines)
R7C3+R8C3=10
R6C4+R6C5+R6C6=20

And I guess that it would be possible to solve this puzzle with these both techniques added.

And in your both jigsaw killers above in this discussion there are also many possibilities to use these techniques.

The House-Cages-Difference and the Cages-House-Difference can also used without the restriction of the cut set to the cardinality of <4. This would result in a logical technique, but it would be less human-like. But with this generalisation it would solve all innie-outie-things I saw on killer technique pages and most of cage split I saw. But of course there are more complicated possibilities to use the 45-property.

To share also the overlapping techniques I saw we could generalize these techniques a little bit, skipping the disjoint set assumption of the houses which are used and adding the intersection of the houses to the cells which result to the sum. For the picture at http://sudoku.apinc.org/?p=27
with this generalization we would get R5C5 = 90-11-20-21-9-24 = 5

The new techniques could be generalized to more houses. But we must make sure that no cell is in 3 of these houses and we would not take the intersection of these houses (the intersection would be empty) but the cells which are in two of the houses.

Two-Houses-Cages-Difference with Overlapping would be:

For every pair of houses (row, column, nonet) look for all cages which are fully in the union of these sets. Calculate the difference of the values and use this as sum of the difference set and of the intersection.

Cages-Two-Houses-Difference with Overlapping:

For every pair of houses (nonet, row, column) look for the smallest set of cages that contains the union of these houses. Calculate the difference of the values and use this as difference of the sum of the difference set and the sum of the intersection.

These techniques would find some combinations of overlapping and 45. See this picture:

Image

Here says the Two-Houses-Cages-Difference with Overlapping:

R1C5+R2C5+R5C5= 90-(20+9+21+24) = 16

The Cages-Two-Houses-Difference with Overlapping says:

(R1C6+R2C6)-R5C5= (20+20+9+21+24) - 90 = 4

Because of the difference this technique is not so simple as
the Two-Houses-Cages-Difference with Overlapping. Furtunately the simpler one is a generalized overlapping technique too.

If the intersection is empty we would get the 2 rules which I described above.

Pyrrhon
Pyrrhon
 
Posts: 240
Joined: 26 April 2006

Postby Ruud » Thu May 11, 2006 2:01 pm

If I'm right there are only 3 techniques which would be necessary to be implemented into SumoCue so that this program can solve this problem too.


The first technique

Actually, there is no need for strong links. A disjoint group of any size will work, as long as there is a single cell sticking out of the nonet. An example:

Take a look at your jigsaw killer, the cage 19[3] in R123C1. When a naked triple would exist in that cage, the 3 digits can not only be excluded from the remainder of row 1, but also from R234C3. These cells can all see the single cell of the triple sticking out of the nonet.

The second technique

I'm afraid you lost me here. What do you mean by cardinality? The number of cells sticking out? The number of candidates in those cells? Maybe you can walk me through a working example.

(I have not studied the 3rd technique yet)

Thanks for your insights.

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby Pyrrhon » Thu May 11, 2006 3:12 pm

The cardinality of a set is the number of elements. This rule is also valid without this restriction.

Lets look at the Cages-House-Difference technique. Take the upper-righth nonet around R1C9 in my jigsaw puzzle.

For the Cages-House-Difference we take all cages with at least one element in this house. This are the cages 9(2), 28(4) and 30(6)

The difference between the set of the cages and our house is {R2C6, R4C6, R3C9}

We can compute the sum

R2C6 + R4C6 + R3C9 taking the difference of the numbers in the cages and 45 as sum of the elements of the nonet, i. e.
R2C6 + R4C6 + R3C9 = (9 + 28 + 30) - 45 = 22 and use this to solve our killer sudoku.

Looking at the nonet in the upper left you would get: R1C3 + R4C2 + R4C4 = (19 + 7 + 27) - 45 = 8

This works not only with nonets, but also with rows and columns, and with pairs, triples ... of houses.

If you look at C8 and C9 then you have the cages 9(2), 28(4), 18(4), 12(2), 7(2), 10(2), and 22(4).

We get
R8C8 + R8C9 = (9+28+18+12+7+10+22)-(2x45) = 16

For the House-Cages-Difference we take all cages with all cells of the cages are in the choosen house.

Take the left nonet in the upper middle around R1C5. You get 3 cages 7(2), 10(2), 15(2).

Now the difference set is R1C3, R2C6,R3C5.

We get R1C3 + R2C6 + R3C5 = 45 - (7+10+15) = 13 and can use this.

This works also in columns, and rows and with pairs, triples of houses.

Lets look at the first column.

Here you would get 2 cages 17(4) and 11(2). We can say

R1C1 + R2C1 + R7C1 = 45 - (17+11) = 17

And if we take 3 nonets (around R5C1, R9C1, and R9C5 we have the cages 17(4), 27(4), 21(4), 11(2), 14(2), 19(4), 14(4)

We get

R2C4 + R7C5 + R9C7 = 3x45 - (17+27+21+11+14+19+14) = 12.

With these both rules we get the most innie-outie-things which are useable in killer sudoku. I think all killer sudokus in this thread would be solveable with these both techniques.

But there is the situation where the houses aren't disjoint (i. e. they are overlapping). For this case we can use the Two-Houses-Cages-Difference technique with Overlapping. The way ist the same as in the Houses-Cages-Difference but we must also add the cells which are in both houses.

To the first technique. The difference is that R8C7 is not in the nonet. In column 7 there must be digit 9 either in R8C7 or in R9C7.
If the 9 is in R8C7 then in R8C4, R8C5, and R8 C6 can't be a digit 9 because they are in the same row. If digit 9 is in R9C7 then in R8C4, R8C5, and R8 C6 can't be a digit 9 because they are in the same nonet.
Pyrrhon
 
Posts: 240
Joined: 26 April 2006

Postby Ruud » Thu May 11, 2006 4:10 pm

Thanks for the extended explanation.

I'm already using this technique in SumoCue, but with the restriction that all the outies are buddies. Innies are always buddies, of course.

In your first example:
R2C6 + R4C6 + R3C9 = (9 + 28 + 30) - 45 = 22

The 3 cells can contain {994}, {985} or {976}, so candidates 1,2,3 can be eliminated.

In your second example:
R1C3 + R4C2 + R4C4 = (19 + 7 + 27) - 45 = 8

The 3 cells can contain upto {116}, so 7,8,9 can be eliminated.

This solves the puzzle without a dance.

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005

Postby Pyrrhon » Thu May 11, 2006 5:17 pm

Okay, my suggestion was to take only sums up to three summands because this is what humans can use without problems and this would concentrate the whole to interesting sums. (I know in concrete cases more summands are reasonable.) All my examples of both techniques are not taken by SudoCue. And it seems the overlapping technique also not. You could have some more restrictions.

If you starts with the houses and look for both cage sets you have a simple heuristic as human and as a computer to find them. If you use all three techniques you have most of 45- and overlapping work. Only a part of cage splitting is in the rest.
Pyrrhon
 
Posts: 240
Joined: 26 April 2006

Postby Ruud » Sat May 20, 2006 6:15 pm

I made a new symmetrical Jigsaw Killer.

How about posting one weekly on my website: jay or nay:?:

To help you make up your mind:

Image

Ruud.
Ruud
 
Posts: 664
Joined: 28 October 2005


Return to Sudoku variants