Killer Swordfish example

IJ · Posted: Mon Apr 18, 2005 2:15 pm Post subject:

Yes, a Jacko! Rubylips and I had a debate about what Nishio was on the previous incarnation of this site, I thought it was a pattern based resolution (as per all the other known methods), Rubylips thought it was a technique of focussed T&E. To avoid confusion, and to stop having the argument, we ended up deciding that I'd get to name the pattern, and I chose "Jacko". I could start another thread to discuss it if you're interested, though I've only ever seen one puzzle where it came up...

Simes · Posted: Mon Apr 18, 2005 2:25 pm Post subject:

Well I never did get my head around Nishio, and I'm still struggling to understand the reasoning behind swordfish.

Is the jacko similarly complex?

rubylips · Posted: Mon Apr 18, 2005 2:36 pm Post subject:

You're completely right about the elimination of the 7 in (1,1) - a recent 'performance enhancement' Embarassed

in my code (unrelated to Swordfish) led me to miss this. (The code ran very fast, though!)

Let's forget that example entirely.

IJ · Posted: Mon Apr 18, 2005 2:55 pm Post subject:

Well, the Jacko only involves 4 digits, but their relationship is a little complex - I'll start a new thread rather than muddy this one.

The way I convince myself that the swordfish is right is by thinking of it as a staircase:

A * * D
* * C d
* B c
a b

You need all the columns and at least one of the rows to have only two places for the given digit. The columns are as shown, and let's say it's the bottom row that has only two places (a & b).

So, starting from the bottom, and going anti-clockwise, say a=true (has the digit), this means that b=false, so B=True, so c=false, C=True, d=False, D=True.

To show what happens when a=false, start in the same place, but go the other way, so A=true, D=false, d=True, C=False, c=True, B=False, b=True.

In both cases we have shown that one of the two places on each row must be true (e.g. B or c, C or d), so that digit can't appear elsewhere on the row.

It's a small leap from there to convince yourself that it doesn't actually need to look like a stair case to work, and it doesn't matter which of the rows has only two instances.

Hope this helps, though I suspect it might just confuse things further...

PS Rubylips - don't worry - we've all been there!

AMcK · Posted: Wed Apr 20, 2005 6:01 pm Post subject:

So this is where you're all lurking now!

Colouring also seems to work OK on killer swordfish and prime suspect

Here's Prime Suspect

AMcK · Posted: Wed Apr 20, 2005 9:56 pm Post subject: Programming colouring/swordfish

What I like about the colouring algorithm is that there is no complex reasoning - it just colours the conjugate pairs in complementary colours then gradually simplifies the colour map by discovering that colours are identical. Here are the relevant steps leading to the two reductions in Prime Suspect.
Starting from

rubylips · Posted: Wed Apr 20, 2005 11:48 pm Post subject:

Does the Colouring Algorithm cope with the four Nishio examples that appear in the '(My) Nishio definition' topic?

AMcK · Posted: Thu Apr 21, 2005 8:05 am Post subject: Colouring, Nishio and slicing

Sadly, colouring isn't able to find any reductions in your new set of 4 Nishio patterns - with the old easy pattern 3 removed, the old 4 renamed as 3 and a new 4th. It doesn't surprise me on reflection because colouring is merely a generalisation of X-Wings and an alternative method for swordfish and cannot therefore do "what if" lookahead like Nishio. I need to look much harder at your Nishio examples to see if there's a colouring method that might legitimise its single-step breadth-first "guessing" approach. However, I am doubtful.

There's another approach I've been working on. I'll have to put it down for a few days because of some urgent paid work so I'll share it tentatively.

Clearly it is not feasible to enumerate all possible valid and completed suduko 9x9 grids. However, is is feasible to enumerate all possible valid 3x9 slices, if you assume that box 1 is
123
456
789
and that slices for other values in box 1 can be derived by simple 1..9 renumbering. I have generated all 2,612,736 of them in an 285MB Access database. (In fact, there are less if you take advantage box 2/3 symmetries but I haven't grappled with that yet).

A possible solution method would then be to simply search the database for a set of 6 interlocking 3x9 patterns that, when renumbered, match the puzzle. Using SQL alone, I can now match completed puzzles in a few seconds. I know how to program the matching of partial puzzles but have no idea of potential speed, either with SQL or in-memory indexing.

Clearly, the legitimacy of this method is dubious and offers no hope for a new manual technique. Although it requires some database searching because it's using the 3x9 slice space optimisation, it isn't guessing in the conventional sense, since it already knows all the solutions and is simpy trying to match them to the puzzle. I'll keep you posted.

Andrew

coconut · Posted: Mon May 16, 2005 8:27 am Post subject: killer swordfish

In the (second, so far undisputed) killer swordfish example of rubylips, my program indicates an x-wing followed by anothe x-wing. My numbering is (column,row) which is the standard in mathematics (linear algebra and matrix theory). After some standard processing by my program,

number 7 is mutually exclusive to (3,8) and (3,9)
number 7 is mutually exclusive to (3,8) and (5,8)
number 7 is mutually exclusive to (3,9) and (5,9)

Thus number 7 can be eliminated from (5,1) and (5,2)

This in turn gives an another x-wing

number 7 is mutually exclusive to (2,1) and (2,2)
number 7 is mutually exclusive to (2,2) and (6,2)
number 7 is mutually exclusive to (6,1) and (6,2)

Thus number 7 is not present in (4,1) which gives number 5 as the occupant of (4,1).

If you dont get these x-wings, then I am doing a step which is not in your programs.

coconut

coconut · Posted: Mon May 16, 2005 1:33 pm Post subject:

I am so sorry; my numbering is (row,column).

coconut

Animator · Posted: Mon May 16, 2005 3:53 pm Post subject:

You don't really need an X-wing to exclude the 7's from r5c1 and r5c2. If you look at box 6, then you will see that the only possible place for a 7 is on row5. Yes there is an X-wing too (or atleast in theory) but it's irrelevant.

Also, I'm currently re-solving it, and my first question is: why did you exclude the 7 from r4c1?

And, why do you say: 'number 7 is mutually exclusive to (6,1) and (6,2)' ? A 7 can occur in r6c1, r6c2, r6c4 and r6c6...

coconut · Posted: Tue May 17, 2005 2:03 pm Post subject: swordfish example of rubylips

Animator is right and I was wrong; (a) I cant exclude 7 from r4c1 and (b) 7 can occur in r6c1, r6c2, r6c4 and r6c6.

Is there a rule book with fomal definitions (e.g. for x-wing, swordfish) which can be used to justify any step?

Tempbow

coconut · Posted: Fri May 20, 2005 8:03 am Post subject:

Are there problems which can be solved only via jellyfish or squirmbag (without nishio, of course) ?

coconut

AMcK

Thanks for the definitions of X-wing, Swordfish, Jellyfish, Squirmbag ...

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 ONE given digit. 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 digit (except in the defining cells!).

As stated, they form a 3-level hierarchy sitting above the traditional 3 rules. However, there may be quite different methods of logical analysis just waiting to be discovered that cut across this hierarchy.

It seems to me that colouring is a superset of all of these - and more - because it analyzes ALL the relationships threads between conjugate pairs of candidates in rows, columns and boxes, no matter how long and convoluted they may be. X-wing, Swordfish, Jellyfish and Squirmbag all limit themselves to regular row/column configurations of conjugate pairs.

Do you have examples of Jellyfish and Squirmbag that I could use to check the colouring solver? It would be good to convince myself.

AMcK