Foreword
Here is my attempt to cover the bare bones of fish patterns in a very condensed overview mainly of tarek's The Ultimate Fish Guide thread with more than 40 pages.
It arises from a realisation that my knowledge of fish was incomplete and misconceived in places, as demonstrated by some recent posts of mine (now amended to avoid confusing others), and the best way to understand a subject, is to try to explain it. Very little is original but perhaps some of my viewpoints may provide brain food. I've soap-boxed and used personal terms for some things, but for anyone who finds these unacceptable it should be simple enough to search-and-replace them in a copy.
Terminology
Fish patterns relate to a single digit in a puzzle only, called the fish digit.
A sector is a set of cells which is governed by a Sudoku "exactly one" rule. For vanilla Sudokus sectors equate to houses.
A fish pattern is composed of two sets of sectors a base set of size N and a cover set size M, that intersect each other.
The difference in the size of the sets, M – N, is k or the k-rank of the fish.
Basic Fish have a base set of sectors all of one house type and a cover set of sectors all of another.
Fanken Fish have one set restricted to non-intersecting rows and boxes and the other to non-intersecting columns and boxes.
Mutant Fish have base and cover sectors that can contain any mix of house types.
Cycling Fish are NxN fish where simple colouring of the intersections of the two sets of sectors shows they can't hold N truths.
Different names have been coined for NXN fish according the value of N, but they only tax the memory, and are omitted here. For these and other fish terms see tarek's opening post < here > in his Ultimate Fish Guide.
Notation
A fish is notated using (Fish_Digit)NxM-(Type)Fish:base_sector_list\cover_sector_list
If M = N, xM can be omitted. Type can also be omitted.
Cell Types
Using b and c for the number of base and cover sectors containing a cell, the different cell types are:
Vertex Cells. : b = c (Body Cell: b & c > 0, External Cell: b & c = 0)
Fin Cells. . . . : b > c
Spot Cells. . . : b < c (previously called PE cells)
Empty Cells....: Those where the fish digit doesn't appear as a candidate.
Spot and fin cells may be prefixed with "d-", the absolute difference between b & c.
PEs (Potential Exclusions) have become to be known as the candidates that would be excluded when an Almost pattern is true, but when a fish is true some (b < c) cells may survive.
Construction and Elimination Rules
These rules are different for NxN and NxM fish.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
NxN Fish
Construction Rules
1. No sector can be used more than once in the combined base and cover sets
2. Each base and cover sector must contain at least one body cell.
Elimination Rules
The number of sectors satisfied by fin and spot cells must balance hence:
1. If there are no fin cells all spot cells are false
2. Any spot cell that would exclude all fin cells is false
3. If only one Fin cell with b-c = d can be true, then all spot cells with c-b > d are false
(These rules are stated as they normally occur, but they can be reversed by swapping over the spot and fin terms.)
Informal Proof
The completed pattern must satisfy N base and N cover sectors. If a subset of true cells satisfies more sectors in one set than the other, then a second subset must exist that will compensate for the misbalance. Therefore no subset can be true that will create a misbalance larger than the capacity of the remaining cells to compensate. The elimination rules apply this inference for a single cell subset.
--------------------------------------------------------------------
NxM Fish
Construction Rules
1. Sectors can be used more than once in the different sets.
2. Each sector of one type must intersect a sector of the other type.
3. The k additional cover sectors must be used to ensure no fin cells exist in the pattern.
[b]Elimination Rules
Any subset of true cells can only satisfy k more cover sets than base sets at most hence:
1. Spot cells with (c – b) > k are false
Informal Proof
The truths the pattern will eventually hold must satisfy N base sectors and N + k cover sectors. By the construction rule, no digit in the pattern can satisfy more base sectors than cover sectors. Consequently the total difference between the number of cover and base sectors satisfied by any subset of true digits cannot be greater than k. The elimination rule applies this inference to a single cells subset. (If an eliminated digit were true, when all the cover sectors were satisfied, at least one empty base sector would remain.)
--------------------------------------------------------------------
Pattern Inferences
The inferences used to develop both these proofs can be incorporated into AICs. For an NxN fish a node consisting of all the body cells is true when it holds N truths. For an NxM fish, the fish is true when no spot cell has c-b > k, but this is less useful.
Example 1
- Code: Select all
| c | b | c | Box
--|----------|----------|----------|- -- - b = Base sector
| . s . | . / . | . s . | c = Cover sector
b | / X / | / / / | / X / |
| . s . | . / . | . s . | / = Empty
--|----------|----------|----------|- -- - . = External
| . s . | . / . | . s . |
| . s* . | . f . | . s* . | X = Body
| . s . | . / . | . s . | f = Fin
--|----------|----------|----------|- -- - s = Spot
| . s . | s X s | . s . |
b | / X / | X / X | / X / | . c . * = Elimination
| . s . | s X s | . s . |
--|----------|----------|----------|- -- -
This grid illustrates the difference between the NxN and NxM treatments.
3-MFish:r28c5\c28b8 = Fin:5c5 => Spots:r5c28 <> fish digit (the one shown)
3x4-MFish:r28c5\r5c28b8 => 2-Spots:r5c28 <> fish digit
As a 3x3 fish, the two eliminated spot cells both see the only fin cell and so can be eliminated under rule 2.
As a 3x4 fish, an extra cover sector is needed that contains the 1-fin:r5c5 to make it a body cell. This will increase the k-rank to 1. By using r5 as the extra cover sector, the 1-spots r5c28 become 2-spots and so are still eliminated under the different rule. If r5c5 was a 2-fin then two extra r5 cover sectors would have been needed to achieve the eliminations (as permitted by construction rules).
The same eliminations can also be achieved using a 2x2 Fish embedded in an AIC using external cells (underlined).
2-Fish:r28\c28 = r8c46 – r79c5 = r5c5 => r5c28 <> fish digit.
Of the three alternatives, the easiest one to digest is the embedded 2x2 fish, but the most concise to notate is the 3x4 fish.
Historically fish patterns used in conjunction with external supporting AICs have been called kraken fish, with r5c5 being called a remote fin, but opinions differ about the correct use of these terms, and when the external chains have more than 2 links the terminology gets over-stretched. Note too that r79c5 is an external node that is needed but isn't identified in the pattern definition. It would be clearer if the fish term was confined to the occupied cells in the defining sectors, and to require any supporting chain to be properly notated.
However, provided no non-fish digits are involved, using NxM fish, overcomes these objections. The extra paths can be included in the pattern by adding a cover sector for every weak link and a base sector for every strong link in the chain(s). This may then produce sectors that occur more than once in the base and cover sets. Pattern transformation methods (described later) may then possibly simplify the resultant combination of sectors used.
Example 2 – Cycling Fish
......7...2.1...3...9.5..8...89......7...45..3......1.6....84...1..7..9...53....2#r4c1<>4#NoFish039
- Code: Select all
| b b | b b | | Box
--|----------|----------|----------|- -- - b = Base sector
| . f f | f f / | / . . | c = Cover sector
c | s / X | / X / | / / s |
c | s X / | X / / | / / s | / = Empty
--|----------|----------|----------|- -- - . = External
| . f / | / / / | / . . |
| / / / | / / . | / / / | X = Body
| / f f | / / / | / / . | f = 1-Fin
--|----------|----------|----------|- -- - F = 2-Fin
| / / / | / / / | . / / |
c | s / X | X / / | / / / | s = 1-Spot
c | s X / | / X / | / / / | S = 2-Spot
--|----------|----------|----------|- -- - $ = 3-Spot
(4)4-Fish:c2345\r2389
This is an example of an impossible cycling fish (we know fish can't ride bikes). It's taken from < this collection > of NoFish, grids with template eliminations that can't be replicated using fish. The body cells lie on diagonals in boxes 1,2,7,& 8, three on / diagonals and one on a \ diagonal. These unequal odd/even parities are a tell-tale that simple colouring of the body cells will lead to a contradiction, and so they can't hold 4 truths.
As the fish is impossible, at least one fin and one spot cell must be true. There are therefore strong links between any two partitions of either of these cell sets.
r4c8 = r46c9 – Spots:r23c9 =[Cycling 4Fish:c2345\r2389]= Spots:r2389c1 => r4c1 <> fish digit.
Pattern Transformations
To find an equivalent pattern advantage is taken of two sector manipulations that have no effect on the overall coverage of base and cover sets.
1: The same sector can be added to or subtracted from both sets.
2: A band that is completely contained in a set can be expressed either as 3 box sectors or 3 line sectors.
To demonstrate how the 3-Mutant Fish above can be transformed so that the base set uses rows and boxes and the cover set uses columns and boxes:
- Code: Select all
*--------------------*-------------------*
| Base Set | Cover Set |
*------------------*------*------*------*-----*-------*-----*
| Operation | R | C | B | R | C | B |
*------------------*------*------*------*-----*-------*-----*
| | 28 | 5 | - | - | 28 | 7 |
| 1 + c46 | 28 | 456 | - | - | 2468 | 7 |
| 2 substitute c/b | 28 | - | 257 | - | 2468 | 7 |
| 3 – b7 | 28 | - | 25 | - | 2468 | - |
*------------------*------*------*------*-----*-------*-----*
As the cover set consists of columns and boxes, the base set needs to be transformed to consist of rows and boxes
Step 1 adds columns 4 & 6 to both sides so the base set entirely contains stack 2.
Step 2 substitutes the stack 2 columns with boxes in the base set.
Step 3 simplifies the result by removing box 7 from both sets.
This produces a quasi-franken fish, quasi because r2 and b2 in the base set intersect.
The same procedure could be used if necessary to transform any rows in the cover set to boxes so any mutant fish can be transformed into a franken or quasi-franken fish usually of a different size and possibly using repeated instances of the same sector.
Hidden Patterns
The hidden pattern for any combination of base and cover sets will show the cells that must be empty for the pattern to be valid and the exclusion cells it provides. Standard grid transforms can then be applied to present the hidden pattern as an exemplar.
Method:
- Code: Select all
1. Convert the fish to the NxM format if necessary
2. Mark each of the 81 grid cells according to their b and c values:
'/' = (b > c) the cell must be empty as it would break the NxM construction rule.
'*' = (c – b > k) the fish digit can be excluded in accordance with the NxM elimination rule.
'X' = (c – b <= k) & (c > 0) a pattern cell
"." = (c = b = 0) an external cell
Two base and cover sets that give identical empty and exclusion patterns are then equivalent. However two non-equivalent fish patterns may provide same eliminations for a particular puzzle when its pattern of empty cells covers both cases and when any elimination cells unique to one of the patterns are already empty.
Other Fish Terms
An NxN <sashimi> fish is one which if true could be solved either fully or in part (ie it would degenerate). Often this is because only one body cell exists in one or more of the defining sectors. However, this feature doesn't appear to directly provide any additional eliminations.
A remora fish is one that is contained within another with eliminations that may only become exposed when some sectors are removed. There is nothing strange in different fish patterns providing different eliminations in the same grid though, and the only remarkable thing here is that one completely contains the other.
Dicsussion
With practice it's possible do develop an eye for spotting basic and franken NxN fish, but this is beyond the capabilities of most for mutant and NxM fish. Furthermore the bigger the pattern, the lower the chances of finding a telling elimination will be. For manual solvers therefore, looking for these fish varieties should be considered measures of last resort. However, manual solvers will be far better than computers at recognising how the inferences from fish patterns combine with others that exist in a puzzle.
For solving programs implementing NxM fish, allowing multiple instances of the same sector would increase the number of combinations to check considerably. This can possibly be avoided in two different ways:
1: Perform a NxN search and only when a single fin node is found, allow further cover and duplicated sectors to be used.
2: Perform a NxN+k search but prohibiting the use of any sector more than once.
Strategy 1 assumes that all fish eliminations can be found using single digit nets.
Strategy 2 assumes that all combinations that involve the repeated use of sectors can be transformed into ones that don't (which is unproven as yet).
Strategy 1 would involve more coding but should run faster. Template checking/POM may well be faster than either, but is rather unsatisfactory as it gives no clue to a reader how the eliminations may be found using logic – this point recurs later.
In 2007 < ronk posted > this puzzle which serves well as a test bed for any fish finding algorithm as there are several possible fish definitions that will make the same three eliminations..
- Code: Select all
2 . . | . . 2 | . 2 2
2 . . | 2 2 . | . . 2
. . . | . 2 2 | 2 . .
-------*-------*-------
. . . | . . 2 | 2 . .
. . 2 | 2 . . | 2 . .
. . 2 | 2 . . | . . 2
-------*-------*-------
. . . | 2 . . | 2 2 .
. . . | . 2 2 | 2 . 2
. 2 . | . . . | . . .
It contains the following fish:
(2)2-Fish:r34\c67 = r3c5 => r1c6 <> 2 (\b2)
(2)3-Fish:r348\c567 = r8c9 => r7c7 <> 2 (\b9)
(2)4-Fish:r348b6\c5679 = r4c7 - r3c7 = r3c56 => r2c5 <> 2 (r3\c7b2)
Interestingly, the 2-fish appears as a remora in the 3-fish, and both are remoras in the 4-fish which would make the same eliminations as both plus the additional one shown.
The sectors shown in brackets are the ones to add to produce the NxM form. These are found by following the chain(s) and adding cover sets for the weak links and base set for the strong ones. This is simpler than the method described by Obi-Wahn towards the end of <this post> about the same puzzle. Converting the 4-fish to a 5x6 fish this way uses r3 twice in the base set and c7 twice in the cover set, but this can be transformed to use single instances only to (2)5x6-MFish:r348c8b1\r12c567b1 giving the same result as Obi-Wahn but by a different route.
Although the transformed 5x6 fish avoids all awkwardness regarding kraken fish and remote fins, it obscures the logic. If the intention is to show readers how they could find the solution for themselves, then it fails.
TAGdpbFishBones
[Edit Aug 20th 2013] corrections made as a result of exchanges with DAJ and Pat
[Edit 2 Jul 2016 Tag added]
