The New Sudoku Players' Forum

[arcilla]

A while ago, when learning about FISHes, it occurred to me that one could look at them in a different way.

I'm not proposing a new solution method -- I wish I were --, but it might help to simplify theory. I couldn't find it mentioned in any sudoku web site or forum I studied. Maybe I didn't try hard enough, but the amount of information is so incredibly large! Or maybe it's just so obvious or useless that nobody bothers to mention it. In that case: sorry for wasting your time, but don't fillet me! Actually, I would expect that programmers use this to try and find fishy objects.

The idea is, that for most 'normal' fishes (for instance where boxes do not come into play, as in 'franken' types, if I understand them correctly), if you administer them in a certain way, they are equivalent to naked or hidden pairs, triples, quads, etc. The administration is simple. Make a list of nine cells, like a Sudoku row. In cell n (1..9) write the (row-)numbers (1..9) of the cells in column n that contain the candidate.

An example (including solved singles). It might not be a viable configuration in real sudoku life, but that's not the point.

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


Derived row:

Code: Select all

(57)(49)(1)(57)(469)(368)(459)(2348)(28)

An X-wing shows up as a naked pair of 5 and 7, pointing to a removable 5, and a sword fish as a hidden triple of 2, 3 and 8, where a 6 and a 4 can be removed.

You can also make a list of column numbers:

Code: Select all

(3)(89)(68)(2578)(147)(56)(14)(689)(257)

Here the X-wing shows up as a hidden pair and the swordfish as a naked triple.

As far as I can see finned fish are equivalent to almost locked sets (and can therefore be attacked analogously).

You can of course make an 'associated sudoku' with each row m (1..9) listing the row or column numbers for candidate m. Maybe this might help to find and solve '3d' configurations. In fact, each state of a sudoku being solved can be seen as a multivalued graph, i.e. a set of triples (row, column, candidate). The associated sudoku is the same set, but with a permutation of some coordinates: (candidate, column, row) or (candidate, row, column). The other permutations are pairwise equivalent.

I have tried to bring box-bound links into the picture (representing franken stuff?) but I didn't succeed. The boxnumber of a cell is not an independent coordinate. Also, I still know too little of the very advanced sudoku theory: I'm actually just a happy intermediate sudoku player.

Some people may find the whole idea a step back, as they prefer to look at diagrams instead of collections of numbers. They might try to look at (naked, hidden, almost) pairs, triples, etc. as fishes

I wonder if this is helpful.

[Myth Jellies]

Your way of looking at it seems pretty genius to me. I like it.

[re'born]

arcilla,

This is a very creative approach. Kudos! It gives me hope that I might find a jellyfish or finned swordfish on my own someday.

I have a rather remedial question for you (or anyone else kind enough to point out the obvious to me).

As far as I can see finned fish are equivalent to almost locked sets (and can therefore be attacked analogously).

Here is an example from the newly formed Ultimate Fish Guide:

Code: Select all

5.....1..2...16.8...35....7...4.8.6...6....9..85..32...5.64.9....91.....3......14
 *--------------------------------------------------------------------*
 | 5      479-6  478    | 23789  2789   2479   | 1      234    2369   |
 | 2      479    47     | 379    1      6      | 345    8      359    |
 |#14689 *1469   3      | 5      289    249    |*46     24     7      |
 |----------------------+----------------------+----------------------|
 | 179    12379  127    | 4      2579   8      | 357    6      35     |
 | 47     2347   6      | 27     257    1      | 34578  9      358    |
 | 479    8      5      | 79     6      3      | 2      47     1      |
 |----------------------+----------------------+----------------------|
 | 178    5      1278   | 6      4      27     | 9      237    238    |
 | 4678   2467   9      | 1      3      27     | 678    5      268    |
 | 3     *267    278    | 2789   2789   5      |*678    1      4      |
 *--------------------------------------------------------------------*

 

The row placements of 6 (which should be viewed as a column vector) are
R_6: [(29)(6)(127)], [(8)(3)(5)], [(4)(1279)(27)]

I added the []'s to help denote the blocks which seems important to me.

R_6[3,9] (the third and ninth entries) form an almost locked set, with the 1 in R_6[3] being the obstruction to a naked pair (and hence the corresponding x-wing). The conclusion, it seems to me, is that in general you could remove a 2 from any of R_6[1,2] since any elimination must occur in the same block as the obstruction and must also be in the same triple as the obstruction (the triples are {1,2,3}, {4,5,6}, {7,8,9}, though this is just a numerical consequence of needing to be in the same block as the obstruction).

First, is this the correct way to view the elimination of the 2 in R_6[1] (or equivalently of the 6 from r1c2)?

Second, if instead you take the column placements of 6:

C_6: [(38)(1389)(5)], [(7)(6)(2)], [(389)(4)(18)],

then we see an almost locked set in C_6[1,7] with 9 being the obstruction to the naked pair. Again, I would think that this implies that one could remove an 8 from any other entry in the third block of C_6 (since that is where the obstruction is), namely remove the 8 from C_6[9].

Code: Select all

 *--------------------------------------------------------------------*
 | 5      4679   478    | 23789  2789   2479   | 1      234    2369   |
 | 2      479    47     | 379    1      6      | 345    8      359    |
 |*14689  1469   3      | 5      289    249    |*46     24     7      |
 |----------------------+----------------------+----------------------|
 | 179    12379  127    | 4      2579   8      | 357    6      35     |
 | 47     2347   6      | 27     257    1      | 34578  9      358    |
 | 479    8      5      | 79     6      3      | 2      47     1      |
 |----------------------+----------------------+----------------------|
 | 178    5      1278   | 6      4      27     | 9      237    238    |
 |*4678   2467   9      | 1      3      27     | *678   5     -268    |
 | 3      267    278    | 2789   2789   5      | #678   1      4      |
 *--------------------------------------------------------------------*

 

Of course, that is exactly what the theory of finned x-wings tells you can be done and while it is not mentioned in that thread, it very well could have been (of course, it isn't needed after the first elimination). So this is very nice and was terribly easy for me to spot using your numerology. My question is how should I see the first elimination using C_6 (or the second elimination using R_6)? It seems I could use almost hidden sets and get the deduction, but is there a faster way?

To be more precise about how I would see it, consider again

R_6: [(29)(6)(127)], [(8)(3)(5)], [(4)(1279)(27)].

R_6[3,8,9] is an almost hidden set (with hidden candidates 1 and 7) with the obstruction to a hidden pair being the 7 in R_6[9]. Then you can remove any 9 from an entry in the third block, i.e., a 9 from R_6[8]. Is that how you would see it?

[arcilla]

Sorry for not replying earlier. I've recently moved to the south of Spain and have no permanent internet connection yet (Telefonica!). At most once a day I go to this wireless hotspot to send and read my email and forums. I'll save your posting, study it at home and get back to you tomorrow! It's rather coldish here these days.

[arcilla]

rep'nA:

I much appreciate your (and Myth Jellies') kind comments (thanks!) but as I said I'm still too unfamiliar with the fine points of almost/finned techniques myself, unfortunately. But as far as I understand your exercise it seems to me that with the 'inverted' representation, one can indeed more routinely (than otherwise) check the 'almost whatever' subsets of a quad such as R_6[1,2,7,9], to see if these subsets can lead to something useful. I hope this was the message in your posting

[re'born]

Here is another example taken from the Ultimate Fish Guide.

# Sashimi Swordfish digit 3

Code: Select all

003400000000025009040700060801000090070050010060000703080006020600170000000003500
.------------------.------------------.------------------.
| 259   259   3    | 4     6     189  | 128   578   12578|
| 7     1     6    | 38    2     5    | 348  #348   9    |
| 259   4     8    | 7    *139   19   |-123   6     125  |
:------------------+------------------+------------------:
| 8    *235   1    | 236  *34    7    | 246   9     245  |
| 2349  7     249  | 23689 5     2489 | 2468  1     248  |
| 2459  6     2459 | 289   1489  12489| 7     458   3    |
:------------------+------------------+------------------:
| 349   8     479  | 5     49    6    | 1349  2     147  |
| 6    *2359  2459 | 1     7     2489 | 3489 *348   48   |
| 1     29    2479 | 289   489   3    | 5     478   6    |
'------------------'------------------'------------------'


It took me quite a while to make this deduction initially, not because of the logic, that is pretty straight forward, but because even if somebody tells you that the puzzle solves with a Sashimi Swordfish and even if somebody tells you "hint, hint, look at 3", it may still be difficult to reel in the fish. On the other hand, converting the '3' placements into the Arcilla matrix, we get:

C_3: [(57),(48),(1)], [(245),(34),(9)], [(2378),(28),(6)]

It is reasonably easy to spot the ALS in C_3[2,5,8] where the 2 in C_3[8] is an obstruction to the ALS being a (degenerate) naked triple. Therefore, we can remove any 1 or 3 from different entries in the same block, i.e., we can remove the 3 from C_3[7]. This translates to deducing r3c7 <> 3. On the other hand, the not-so-bright examiner (e.g., me) will ask why we didn't take the 3 in C_3[5] to be the obstruction. This is perfectly legitimate and implies that we can remove any 1 or 2 from different entries in the same block, i.e., we can remove the 2 from C_3[4]. This translates to deducing r2c4 <> 3 and corresponds to the sashimi swordfish:

# Sashimi Swordfish digit 3

Code: Select all

.------------------.------------------.------------------.
| 259   259   3    | 4     6     189  | 128   578   12578|
| 7     1     6    |-38    2     5    | 348  *348   9    |
| 259   4     8    | 7    #139   19   | 123   6     125  |
:------------------+------------------+------------------:
| 8    *235   1    | 236  *34    7    | 246   9     245  |
| 2349  7     249  | 23689 5     2489 | 2468  1     248  |
| 2459  6     2459 | 289   1489  12489| 7     458   3    |
:------------------+------------------+------------------:
| 349   8     479  | 5     49    6    | 1349  2     147  |
| 6    *2359  2459 | 1     7     2489 | 3489 *348   48   |
| 1     29    2479 | 289   489   3    | 5     478   6    |
'------------------'------------------'------------------'


Naturally, either deduction implies the other so you don't need both, but it is very pleasing to see both fish constructed so easily, especially for someone like me who historically bought his fish at the fish market, pre-gutted, sliced and diced.

[Edit: Per Mike's request, I made the above Arcilla matrix accurate. I also changed the first deduction from r7c3<>3 to r3c7<>3. This has the added advantage of being the correct deduction.]

[Mike Barker]

Arcilla, this is really cool and makes finding fish easy. Thanks for sharing. rep'nA, there is also a swordfish in c248 which implies r4c5<>3.

[re'born]

Thanks Mike. I've edited my post above. Oh, and thanks for the extra finned swordfish. It was scrumptious.

[Pat]

when learning about FISHes,
it occurred to me that one could look at them in a different way.

it might help to simplify theory.
I couldn't find it mentioned in any sudoku web site or forum I studied.
Actually, I would expect that programmers use this to try and find fishy objects.

for 'normal' fishes, if you administer them in a certain way,
they are equivalent to naked or hidden pairs, triples, quads, etc.

The administration is simple:
make a list of nine cells, like a Sudoku row;
in cell n (1..9) write the (row-)numbers (1..9) of the cells in column n that contain the candidate.

hi arcilla,
here are some references which may be relevant to the history of this idea---

my solver treats things such as 'the possible placements of digit 7 in column 4' the same way as 'the possible values of cell (3,5)'.

This means that matched pairs is treated the same as X-wings.
For example, an X-wings in my solver gives the output:

Code: Select all

 Must have number 9 at (1,5) (and number 9 at (9,8))
 or number 9 at (9,5) (and number 9 at (1,8))
 reducing options for digit 9 in column 5
 Must have number 9 at (1,8) (and number 9 at (9,5))
 or number 9 at (9,8) (and number 9 at (1,5))
 reducing options for digit 9 in column 8

and a matched pair gives the output:

Code: Select all

 Must have number 2 at (1,2) (and number 3 at (1,9))
 or number 2 at (1,9) (and number 3 at (1,2))
 reducing options for digit 2 in row 1
 Must have number 3 at (1,2) (and number 2 at (1,9))
 or number 3 at (1,9) (and number 2 at (1,2))
 reducing options for digit 3 in row 1

In the same way (if I had implemented them) a matched triplet would be equivalent to Swordfish, a matched quadruplet equivalent to Jellyfish, etc.

New n-Wings algorithm finds the 4x4 instantaneously
using row/column occupancy bitmaps

this algorithm, virtually unchanged,
can also be used to reliably find naked and hidden n-tuples

X-wing, Swordfish, Jellyfish
are actually identical in form to finding naked or hidden subsets.
The only difference is that
instead of using digit and position for a certain house (box/col/row),
you're using column and row for a certain digit.

X-wings and swordfish are a positional form of the subset test.
Instead of looking for subsets of digits and positions in a house (box/column/row),
you're looking for subsets in columns and rows.

[arcilla]

See? I already expected other people to have the same idea. And such a long time ago! (In sudoku life.) Thus, so far it didn't have much potential. Thanks Pat for digging this up!

[Pat]

re history — here are 3 more items i had missed in my previous post —

It is well known that the concepts of cell, row, column and block are interchangeable when solving SuDoku.

One important example of this property is the X-Wing, which is a dual of the naked pair:

naked pair -
If the possible placements in a row for two numbers include two cells that don't have other possibilities, then the other placements in the row for the two numbers may be excluded.

X-Wing -
If the possible placements for a number in two columns include two rows that don't have other possibilities, then the other placements for the number in the two columns may be excluded.

The subset solver will also find X-wings and Swordfish,
since those are just positional versions of the subset rule.

X-wing, Swordfish, and these other forms are all just a positional form of naked/hidden subsets

This is what I mean when I say this is a positional form of the subset rule: Naked and hidden subsets both operate on a binary graph of candiate digits and positions within a house. Observe the following:

Code: Select all

       digit
p   1 2 5 6 7 9
o
s 2 X X   X   
i 4   X X   X 
t 5 X   X     X
i 7 X   X X X 
o 8     X     X
n 9 X   X     X



What we have here is a hidden subset, where 2,6,7 appear only in positions 2,4,7. If you take only those 3 columns, you get only 3 active rows. However you can use this same graph with different values to find naked subsets. All you have to do is look for rows instead of columns.

X-wing and Swordfish are the same thing because you can change the labels on the graph. Skipping over any cols/rows where the target digit is accounted for, label the graph with any columns and rows where you aren't sure of the digit's position, and put an X in where any candidates may occur.

— however, i still don't know if the 2005.Jul.19 item is the earliest ever—

~ Pat

[denis_berthier]

A while ago, when learning about FISHes, it occurred to me that one could look at them in a different way.
[…]
The idea is, that for most 'normal' fishes (for instance where boxes do not come into play, as in 'franken' types, if I understand them correctly), if you administer them in a certain way, they are equivalent to naked or hidden pairs, triples, quads, etc. The administration is simple. Make a list of nine cells, like a Sudoku row. In cell n (1..9) write the (row-)numbers (1..9) of the cells in column n that contain the candidate.
[…]
An X-wing shows up as a naked pair […] and a sword fish as a hidden triple.

Arcilla, I was not aware of your remark when I wrote my book, "The Hidden Logic of Sudoku". Otherwise, I would have cited you. You had a great idea. Unfortunately, as I can see from the posts in this thread, nobody seems to have really understood it or pushed it further.

Based on more general ideas of symmetry, I came upon quite the same idea, formalised it. More generally, I introduced rn- and cn- spaces and an associated extended sudoku board to deal with them. I also extended the idea to chains, where it allows introducing completely new types of chains (hidden chains).

You can see more about this on my web pages (http://carva.oeg/denis.berthier) or on the Sudoku UK and Sudoku Programmers Forums.

I have tried to bring box-bound links into the picture (representing franken stuff?) but I didn't succeed. The boxnumber of a cell is not an independent coordinate. Also, I still know too little of the very advanced sudoku theory: I'm actually just a happy intermediate sudoku player.

It's normal that you could not extend your idea to boxes. Only block-free rules can be transposed to the rn- and cn- spaces.
In these spaces, I proved that only Latin Squares rules are valid.

[ravel]

Hi Denis,

There is a typo in your web address, should be http://carva.org/denis.berthier.

In the time i have watched this forum, so far i never heard about a (essentially) new solution technique, which has been published earlier elsewhere (in other forums, books or newspapers).

Since i could not find something about e.g. hidden chains on the web page, please could you tell us, what "hidden" means here ? Does it mean the use of bilocation links or of hidden subsets ?

[denis_berthier]

Since i could not find something about e.g. hidden chains on the web page, please could you tell us, what "hidden" means here ? Does it mean the use of bilocation links or of hidden subsets ?

I announced my book on the following thread:
http://forum.enjoysudoku.com/viewtopic.php?t=5512

About hidden chains, you can also see chapter XV of my book (or of the online excerpt) or { broken link } www.sudoku.org.uk/discus/messages/29/4235.html?1182997993

[ravel]

Thanks for the links.

Nice thread on the discussions forum with an interesting point of view.