Swordfish, Slot Machines and Pomeranians

Advanced methods and approaches for solving Sudoku puzzles

Swordfish, Slot Machines and Pomeranians

Postby tso » Fri Dec 23, 2005 5:54 pm

The Myth of the required tactic.

This is a Pappocom, rated HARD:

Code: Select all
+-------+-------+-------+
| 2 . 7 | . 5 . | 8 . 1 |
| . . . | 3 . 8 | . . . |
| . 8 . | . . . | . 4 . |
+-------+-------+-------+
| 9 . . | 6 . 2 | . . 8 |
| . . . | . 9 . | . . . |
| 6 . . | 4 . 7 | . . 2 |
+-------+-------+-------+
| . 4 . | . . . | . 9 . |
| . . . | 5 . 1 | . . . |
| 8 . 3 | . 4 . | 5 . 7 |
+-------+-------+-------+


It can be solved using nothing but naked and hidden singles. (Which makes me question the rating “hard”, but that’s another issue.)

However, if you want, you can easily find swordfish in 8s on you very first move. The swordfish is marked with plus signs, the exclusion is marked with a minus sign:


Code: Select all
 *--------------------------------------------------------------------*
 | 2      369    7      | 9      5      469    | 8      36     1      |
 | 145    1569   14569  | 3      1267   8      | 2679   2567   569    |
 | 135    8      1569   | 1279   1267   69     | 23679  4      3569   |
 |----------------------+----------------------+----------------------|
 | 9      1357   145    | 6      13     2      | 1347   1357   8      |
 | 13457  12357 +12458  |+18     9      35     | 13467  13567  3456   |
 | 6      135   +158    | 4     +138    7      | 139    135    2      |
 |----------------------+----------------------+----------------------|
 | 157    4      1256   |+278   +23678  36     | 1236   9      36     |
 | 7      2679   269    | 5     -23678  1      | 2346   2368   346    |
 | 8      1269   3      | 29     4      69     | 5      126    7      |
 *--------------------------------------------------------------------*


The fact that there is a “simpler” pattern to be found is misleading. We can have general agreement that singles are simpler than swordfish or that naked pairs are simpler than naked triples -- but the comparative level of complexity of all the patterns is not absolute. Various factors effect the apparent complexity. Forcing chains can be very difficult to find at the beginning of a puzzle but completely obvious at the end. The methods one uses, the specifics of the puzzle and the order one applies each tactic all have there effect. Most solvers consider hidden trips or naked quads a simpler tactic than x-wings and coloring, but the former are more difficult to spot.

Most software solvers look for patterns in a set order according to a somewhat arbitrary choice made by the programmer. A specific sudoku cannot intrinsically “need a swordfish” to be solved, but it can be artificially made to seem that way by pretending there is an obvious logical progression of tactics.

Slot Machines and how they explain the apparent rarity of the 9 cell Swordfish.

I have two black Pomeranians. Everyone we meet says that they’ve never seen a black pom and ask if they are rare. The truth is, Poms come in lots of colors from white to black, all of which are equally common. However, all the middle colors blend together in the non-pom-owner's minds, giving the false impression of rare whites, rare blacks and common everything else.

This effect is exploited in slot machines. Consider a machine with 3 wheels, each of which has 10 positions and only on BAR. To win, you have to get BAR BAR BAR on the centerline. If one, two or three bars are just above or just below the centerline, you lose -- but it looks like you came very close. The truth is, there are 26 of these almost-wins for every 1 actual win.

Consider a swordfish. Each row may contain 2 or 3 cells containing the candidate -- but that’s misleading! Actually, each row has FOUR configurations: xxx, -xx, x-x, -xx. The total number of configurations of the three rows forming a swordfish (not including degenerate cases containing x-wings) is 28: [EDITED: I left out quite a few the first time round.]

Code: Select all
x x x
x x x
x x x


x x -    x x x    x x x
x x x    x x -    x x x
x x x    x x x    x x -

x - x    x x x    x x x
x x x    x - x    x x x
x x x    x x x    x - x

- x x    x x x    x x x
x x x    - x x    x x x
x x x    x x x    - x x


x x -    x x -    x x -    x x -
x - x    - x x    x x x    x x x
x x x    x x x    x - x    - x x

x - x    x - x    x - x    x - x
x x -    - x x    x x x    x x x
x x x    x x x    - x x    x x -

- x x    - x x    - x x    - x x
x x -    x - x    x x x    x x x
x x x    x x x    x - x    x x -


x x -   x x -
- x x   x - x
x - x   - x x

x - x   x - x
x x -   - x x
- x x   x x -

- x x   - x x
x x -   x - x
x - x   x x -



The swordfish with 6, 7 and 8 cells blend together in the solver’s mind, making the lone 9 cell configuration seem less common, when it is possible that each of the 16 patterns might be as common as the next.

Whether these patterns are equally common is unknowable, as it depends on how the puzzle was constructed and in what arbitrary order the solver applies the tactics s/he/it knows.
tso
 
Posts: 798
Joined: 22 June 2005

Postby tso » Sun Dec 25, 2005 12:23 am

I haven't found a Swordfish that has all 9 cells working yet. I'll post it if I do. If anyone else finds one, post it here.

In the mean time, here's a good one. It requires nothing but singles -- then an 8-cell Swordfish -- then nothing but singles. Pure fishy goodness:


Code: Select all
 5 . . | 6 . . | 2 9 8
 3 2 . | . . 8 | . . .
 . . 8 | 7 . . | . 5 3
-------+-------+------
 2 . . | . . 9 | . . .
 9 4 . | . . . | . 1 5
 . . . | 8 . . | . . 9
-------+-------+------
 8 6 . | . . 7 | 5 . .
 . . . | 2 . . | . 6 1
 4 3 2 | . . 5 | . . 7
tso
 
Posts: 798
Joined: 22 June 2005

Postby sheila08 » Wed Dec 28, 2005 8:12 pm

Dear Tsu,

What do you mean by a 9-cell swordfish? Non comprende...

Sheila
sheila08
 
Posts: 27
Joined: 08 July 2005

Postby rubylips » Wed Dec 28, 2005 10:30 pm

tso,

I've tried your puzzle. Singles take me to here:

Code: Select all
 5 . . | 6 . . | 2 9 8
 3 2 . | . . 8 | 1 7 .
 . . 8 | 7 . . | . 5 3
-------+-------+------
 2 8 . | . 1 9 | . . .
 9 4 . | 3 . . | 8 1 5
 . . . | 8 . . | . 2 9
-------+-------+------
 8 6 1 | . . 7 | 5 . 2
 7 . . | 2 8 . | . 6 1
 4 3 2 | 1 6 5 | 9 8 7

   5   17    47 |    6   34  134 |     2   9   8
   3    2   469 |  459  459    8 |     1   7  46
  16   19     8 |    7  249  124 |    46   5   3
----------------+----------------+--------------
   2    8  3567 |   45    1    9 |  3467  34  46
   9    4    67 |    3   27   26 |     8   1   5
  16  157  3567 |    8  457   46 |  3467   2   9
----------------+----------------+--------------
   8    6     1 |   49  349    7 |     5  34   2
   7   59    59 |    2    8   34 |    34   6   1
   4    3     2 |    1    6    5 |     9   8   7

where I find the following chain in the 4s:

Code: Select all
Consider the chain r1c6~4~r1c3-4-r2c3~4~r2c9-4-r3c7~4~r8c7-4-r8c6.
When the cell r1c6 contains the value 4, so does the cell r8c6 - a contradiction.
Therefore, the cell r1c6 cannot contain the value 4.

However, it doesn't leave the puzzle in a trivial state. Nor do I find anything else that's remotely straightforward. I'm sure I've been stupid. Please explain ...
rubylips
 
Posts: 149
Joined: 01 November 2005

Postby Carcul » Wed Dec 28, 2005 11:30 pm

Hi Rubylips.

Rubylips wrote:
Code: Select all
   5   17    47 |    6   34  134 |     2   9   8
   3    2   469 |  459  459    8 |     1   7  46
  16   19     8 |    7  249  124 |    46   5   3
----------------+----------------+--------------
   2    8  3567 |   45    1    9 |  3467  34  46
   9    4    67 |    3   27   26 |     8   1   5
  16  157  3567 |    8  457   46 |  3467   2   9
----------------+----------------+--------------
   8    6     1 |   49  349    7 |     5  34   2
   7   59    59 |    2    8   34 |    34   6   1
   4    3     2 |    1    6    5 |     9   8   7


In your grid above, there is a Swordfish on "4" in rows 3, 6, and 8 that solve the puzzle.

Regards, Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby simes » Wed Dec 28, 2005 11:34 pm

The cells r3c5, r6c5, r3c6, r6c6, r8c6, r3c7, r6c7 and r8c7 form a swordfish of 4s, allowing for eliminations in r1c5, r1c6, r2c5, r4c7 and r7c5.

S
simes
 
Posts: 324
Joined: 11 March 2005
Location: UK

Postby tso » Thu Dec 29, 2005 1:19 am

sheila08 wrote:Dear Tsu,

What do you mean by a 9-cell swordfish? Non comprende...

Sheila



Code: Select all
 
  5     17    47    | 6     34    134   | 2     9     8     
  3     2     469   | 459   459   8     | 1     7     46   
  16    19    8     | 7    [249] [124]  |[46]   5     3     
 -------------------+-------------------+-------------------
  2     8     3567  | 45    1     9     | 3467  34    46   
  9     4     67    | 3     27    26    | 8     1     5     
  16    157   3567  | 8    [457] [46]   |[3467] 2     9     
 -------------------+-------------------+-------------------
  8     6     1     | 49    349   7     | 5     34    2     
  7     59    59    | 2  -->8    [34]   |[34]   6     1     
  4     3     2     | 1     6     5     | 9     8     7     
 


The 8 cells in [brackets] form an 8-cell Swordfish in 4s in rows, eliminating candidate 4s from the rest of the three columns.

If row 8, column 5 contained the candidate 4, we would have the elusive 9-cell Swordfish.
tso
 
Posts: 798
Joined: 22 June 2005

Postby Scott H » Mon Jan 16, 2006 6:33 am

Interestingly, this puzzle contains a second independent order 3 swordfish in 4s. In addition to the 8-cell 3-3-2 swordfish already noted in rows 3,6,8, there's a 7-cell 3-2-2 swordfish in columns 4,8,9 (using rows 2,4,7). I haven't seen this independent non-dual swordfish combination before (not that I've looked very hard).
Scott H
 
Posts: 73
Joined: 28 July 2005

Postby Myth Jellies » Tue Jan 17, 2006 3:17 am

ScottH

That's actually a jellyfish that mirrors the original swordfish. I think you missed the candidate 4's in column 3 (specificly r2c3). It's really a 1-3-3-2 jellyfish in r1247c3489. Every NxN swordfish in rows/columns has a mirror MxM swordfish in colums/rows, where M = (9 - N) - number of solved cells for the digit in question. Here we have two solved digits for 4, so M equals 4. I'm pretty sure there are some cases where the MxM swordfish can degenerate to something less, though (or the NxN swordfish expand to something more).

[edited to fix the formula for M, thanks to Ronk.]
Last edited by Myth Jellies on Tue Jan 17, 2006 1:14 am, edited 1 time in total.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Tue Jan 17, 2006 4:57 am

Myth Jellies wrote:Every NxN swordfish in rows/columns has a mirror MxM swordfish in colums/rows, where M = 9 - number of solved cells for the digit in question.

I just began suspecting they existed in pairs today, so thanks for the formula. A couple of minor points: 1) I think you forgot to include N in your formula, and 2) I see the 2nd jellyfish as a 2-3-3-2 in r1247c3489, not a 1-3-3-2. For 1), the formula appears to be

M + N = 9 - {number of filled cells for the digit in question}
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Tue Jan 17, 2006 5:11 am

Doh, you are absolutely right...I will edit my post.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Myth Jellies » Tue Jan 17, 2006 6:10 am

I suppose since the jellyfish lies in columns instead of rows, it should really be a 2-3-2-2 jellyfish (from left to right)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Scott H » Tue Jan 17, 2006 7:29 am

Myth, look again. My column 4,8,9 swordfish is still there. A rare curiosity I think worth noting.

Sure, adding unnecessary column 3 gives a jellyfish, but the jellyfish is degenerate because it contains my swordfish. You can just as well turn the row 3,6,8 swordfish into a degenerate jellyfish by adding row 1.

Your description suggests you either didn't read my post or didn't see my swordfish. On the off chance you got a different candidate grid, my candidate grid is

Code: Select all
 *-----------------------------------------------------------*
 | 5     17    47    | 6     34    134   | 2     9     8     |
 | 3     2     469   | 459   459   8     | 1     7     46    |
 | 16    19    8     | 7     249   124   | 46    5     3     |
 |-------------------+-------------------+-------------------|
 | 2     8     3567  | 45    1     9     | 3467  34    46    |
 | 9     4     67    | 3     27    26    | 8     1     5     |
 | 16    157   3567  | 8     457   46    | 3467  2     9     |
 |-------------------+-------------------+-------------------|
 | 8     6     1     | 49    349   7     | 5     34    2     |
 | 7     59    59    | 2     8     34    | 34    6     1     |
 | 4     3     2     | 1     6     5     | 9     8     7     |
 *-----------------------------------------------------------*

3-3-2 swordfish A in rows 3,6,8 (using cols 5,6,7).
3-2-2 swordfish B in cols 4,8,9 (using rows 2,4,7).

Myth Jellies wrote:ScottH

That's actually a jellyfish that mirrors the original swordfish. I think you missed the candidate 4's in column 3 (specificly r2c3). It's really a 1-3-3-2 jellyfish in r1247c3489. Every NxN swordfish in rows/columns has a mirror MxM swordfish in colums/rows, where M = (9 - N) - number of solved cells for the digit in question. Here we have two solved digits for 4, so M equals 4. I'm pretty sure there are some cases where the MxM swordfish can degenerate to something less, though (or the NxN swordfish expand to something more).

[edited to fix the formula for M, thanks to Ronk.]
Scott H
 
Posts: 73
Joined: 28 July 2005

Postby Myth Jellies » Tue Jan 17, 2006 10:03 am

Heh, I pretty much jacked up that whole post, didn't I. Swordfish just tend to do that to me.

Anyway, I am not so sure about the rarity of these degenerate cases. I've seen a fair number come up lately. Jeff recently came up with this beauty which contains a jellyfish, swordfish, and an X-wing.

Image
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Tue Jan 17, 2006 12:05 pm

Myth Jellies wrote:I suppose since the jellyfish lies in columns instead of rows, it should really be a 2-3-2-2 jellyfish (from left to right)

We're just going to have to keep a closer eye on you. When I saw the error in the first digit for your original 1-3-3-2, I didn't even look for a second error.:D

Joking aside, I just wanted to add my two cents about "N-fish" (3-swordfish, 4-jellyfish, and 5-squirmbag) degeneracy. The easiest way to recognize degeneracy is to look at the number of candidates in both the columns and rows of the defined(observed) N-fish.

If the N-fish is defined by columns, it must have at least two candidates in each row to be a non-denerate N-fish. In Myth Jellies' preceeding illustration, the jellyfish is degenerate because there is only one candidate in row 4 (r4c8)... and the swordfish is degenerate because there is only one candidate in row 1 (r1c6).

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Next

Return to Advanced solving techniques