Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

NEWS:
A simple algorithm that catches (almost) any FISH
Goto page 1, 2, 3, 4, 5, 6, 7, 8  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
Obi-Wahn

Joined: 21 Aug 2006
Posts: 18
:

Items
PostPosted: Tue Jan 09, 2007 8:42 pm    Post subject: A simple algorithm that catches (almost) any FISH Reply with quote

Hello fellow Sudoku addicts Smile

I'm working for quite some time on my own program that generates and solves Sudokus. I've implemented the basic solving methods for singles, disjoint subsets, locked candidates, classic seafood (x-wing, swordfish, jellyfish), extended seafood (finned and sashimi) and y-wings. I've also included the possibility to process archives of Sudokus and filter it by means of solvability with different sets of methods.
Then I added Ruud's templates to find any conclusions possible by examining only the pattern of a single value. This covers all eliminations caused by hidden singles, locked candidates and any kind of seafood but it also solved many puzzles that couldn't be solved by these methods. It also finds turbot fish for example.
Then I stumbled over the topic about fishes with more than 2 fin cells and realized that my extended seafood algorithm couldn't find it because it only allows fin cells in one row or column respectively. While thinking about how to change my algorithm to cover these suckers, I found the Ultimate FISH Guide which was a real eye opener. There were plenty varieties of fish I didn't even think about but there also was one simple definition that gave me the hint for a new algorithm:

Quote:
in a sudoku grid if any selected cells of a digit's candidates can be mapped as N base sets * N cover sets then we have a FISH......

However since any combination of unit types is allowed as base some clarification is needed:

Rule 1: The base can be any combination of N units (rows, columns, boxes) that don't share any common candidates of the digit in question.
This rule isn't necessary for classic fish because if the base is built by rows only they can never overlap (same applies for columns only).

Rule 2: All the candidates of the base units (the base set) must be covered by a combination of M cover units that aren't already used as base units.
There is no use in sharing the same unit for both base and cover, because this unit can be completely left out reducing the fish to N-1.

Rule 3: If M = N we have a basic (finless) fish which leads to the following conclusions:
- any candidate that is part of a cover unit but not of the base set can be eliminated.
- any candidate that is part of more than one cover unit can be eliminated.

The second type of eliminations doesn't occur on classic fish because units of the same type never overlap.

Now so far you might say that there's not much new in these rules. But the interesting part is how to deal with fins. Basically fin cells are candidates of the base set that are not covered by N cover units. So you need an additional unit to cover the fin cells. Every candidate that belongs to the cover set and the fin unit but not the base set can then be eliminated. Looking at different finned fish in the light of these new general rules, I realized that the fin unit can always be exchanged with any cover unit it shares at least one common candidate with, leading to another fish of the same type with different fin cells but the same eliminations. This discovery brought me to the idea not to distinguish between cover and fin units but to regard them as N + 1 cover units which leads to a simple rule to handle finned fish:

Rule 4: If M = N + 1 then every candidate that is covered by at least 2 of the cover units and is not part of the base set can be eliminated.

After I implemented these rules my fishing algorithm was able to solve about 80% of the remaining template solvable Sudokus that my previous extended seafood algorithm wasn't able to solve. Then I thought about why only N + 1 cover units should be allowed. The maximum number of units that can share the same candidate is 3 (a row, a column and a box). And although I couldn't think of any fish that has fins in 2 different units I couldn't find any compelling reason why this should be impossible. So I decided to give it a try and implemented another rule:

Rule 5: If M = N + 2 then every candidate that is covered by 3 different cover units can be eliminated.

I was all smiles when this addition to my fishing algorithm lead to solving almost all of the remaining template solvable sudokus except for 2. But I actually couldn't see the reason why these 2 didn't surrender because the contradiction was easy to recognize. Here's an example:

Code:

.---------------.---------------.---------------.
| 37   8    6   | 347  27   1   | 5    9    247 |
| 5    4    2   | 79   789  6   | 3    1    78  |
| 1    39   79  | 347  5    248 | 2478 478  6   |
:---------------+---------------+---------------:
| 2    5    478 | 6    3    48  | 1    78   9   |
| 9    6    478 | 147  1278 248 | 278  5    3   |
| 78   1    3   | 5    278  9   | 2478 6    2478|
:---------------+---------------+---------------:
| 4    7    1   | 8    6    3   | 9    2    5   |
| 38   29   5   | 29   4    7   | 6    38   1   |
| 6    239  89  | 129  19   5   | 478  3478 478 |
'---------------'---------------'---------------'

  .  8  . |  .  .  . |  .  .  .
  .  .  . |  .  8  . |  .  .  8
  .  .  . |  .  .  8 |  8  8  .
----------+----------+----------
  .  .  8 |  .  .  8 |  .  8  .
  .  .  8 |  .  8  8 |  8  .  .
 *8  .  . |  .  8  . |  8  .  8
----------+----------+----------
  .  .  . |  8  .  . |  .  .  .
  8  .  . |  .  .  . |  . *8  .
  .  . *8 |  .  .  . |  8  8  8


All the candidate 8s marked with an asterisk can be eliminated. If any of them was correct then r8c1 must be wrong leading to the other two marked candidates being correct. This leads to hidden singles in r2c9, r4c6 and r5c7 which in turn leave no candidates for r3, c5 and b2.
If have a strong feeling that these eliminations should also be possible with some kind of general fish but I'm just not able to see it. Does anybody have any idea or are there simply some very few examples of template eliminations that can't be explained with FISH?


Last edited by Obi-Wahn on Wed Jan 10, 2007 3:36 pm; edited 2 times in total
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 431
:

Items
PostPosted: Wed Jan 10, 2007 12:32 am    Post subject: Re: A simple algorithm that catches (almost) any FISH Reply with quote

Obi-Wahn wrote:
Does anybody have any idea or are there simply some very few examples of template eliminations that can't be explained with FISH?

ronk and I are working on deriving fish from Templates in the Players' Forums. ronk is very good at finding fish, and my puzzle generator supplies him with plenty of Templates patterns to resolve.

I'll direct him to your message here and see if his experience can resolve your pattern in 8s. Odds are, Ruud will read it first and have a handy solution.

As a footnote, ronk has had to come up with some very complicated fish to explain some Templates patterns. Also, he's found that X-Colors can often be used instead, and he's working on finding a correlation.
Back to top
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Wed Jan 10, 2007 3:40 am    Post subject: Re: A simple algorithm that catches (almost) any FISH Reply with quote

Obi-Wahn wrote:
Rule 1: The base can be any combination of N units (rows, columns, boxes) that don't share any common candidates of the digit in question.
Code:

  .  8  . |  .  .  . |  .  .  .
  .  .  . |  .  8  . |  .  .  8
  .  .  . |  .  .  8 |  8  8  .
----------+----------+----------
  .  .  8 |  .  .  8 |  .  8  .
  .  .  8 |  .  8  8 |  8  .  .
 *8  .  . |  .  8  . |  8  .  8
----------+----------+----------
  .  .  . |  8  .  . |  .  .  .
  8  .  . |  .  .  . |  . *8  .
  .  . *8 |  .  .  . |  8  8  8

All the candidate 8s marked with an asterisk can be eliminated.
...
If have a strong feeling that these eliminations should also be possible with some kind of general fish but I'm just not able to see it. Does anybody have any idea or are there simply some very few examples of template eliminations that can't be explained with FISH?

I suspect you need to modify Rule 1 in order to pick up the elimination r8c8<>8. The other two eliminations then follow due to the resultant single in r8c1.

In brief, two base units may share a candidate as long as that candidate is treated as a fin cell.
Code:

 .  .  . |  .  .  . |  .  .  .
 .  .  . |  . *8  . |  .  . *8
 .  .  . |  .  .  8 |  8  8  .
---------+----------+----------
 .  . *8 |  .  . *8 |  . *8  .
 .  .  8 |  . *8  8 |  8  .  .
*8  .  . |  . *8  . |  8  . *8
---------+----------+----------
 .  .  . |  .  .  . |  .  .  .
#8  .  . |  .  .  . |  . -8  .
 .  . *8 |  .  .  . |  8  8 #8

 sashimi mutant squirmbag r4c159b7\r26c38b5 plus fins r8c1 and r9c9, implies r8c8<>8

In this grid, r8c1 is shared by base sectors c1 and b7.

Considering that the mix of rows, columns and boxes in the base and cover sets makes things difficult, I'd very much like to learn your algorithm. As a minimum, would you please consider posting some pseudo-code?
Back to top
View user's profile Send private message
Obi-Wahn

Joined: 21 Aug 2006
Posts: 18
:

Items
PostPosted: Wed Jan 10, 2007 9:00 am    Post subject: Reply with quote

Thank you very much for your input.
But as I see it, if you allow base units to overlap, the whole reasoning for eliminations doesn't work anymore. The point is that in order to fill N base units you need N different candidates, because the base units don't overlap.
Since every base candidate also belongs to a cover unit, this fills at least N cover units. So if you only have less than N cover units covering all base candidates, the puzzle isn't solvable anymore. And that's why in a finless fish you can eliminate every candidate of the cover set that's outside the base set, because it removes a cover unit without removing a base unit. And you can eliminate every double covered candidate, because it removes 2 cover units but only 1 base unit.

[edit]After reading your post again I'm beginning to think you are right. Since we look at the basic fish pattern after removing the candidates in the fin cells, two base units overlapping in a fin don't hurt the basic fish pattern. But I have no idea yet how to include this in my algorithm, since I don't handle fin candidates any different then normal base candidates.[/edit]

But of course I will try to put down my algorithm as pseudo-code. The source code is written in C++, but I'm more than lazy with comments, so it's probably not very easy to understand.

My algorithm is a recursive backtracking algorithm that first builds any possible combination of any number of base units by successively adding units to the base set. After every addition it starts another recursion to find any combination of cover units successively adding units to the cover set.
During all this I use templates to keep track of all candidates of the digit in question, the base set, the cover set, double covered candidates and triple covered candidates. To keep track of the base candidates I also use an array of 9*9 structures that contain pointers to the previous and the next candidate also, so they can form a doubly linked list. This way I can easily access the candidates by their coordinates through the array or add them to and remove them from the list of base candidates using the pointers. The structures also contain information about all units a candidate belongs to, making it easy to find the next cover unit.
The base recursion ends when there are no candidates left that aren't part of the base set yet. It then goes one step back and adds the next unit until all units are tried.
The cover recursion ends when either all base candidates are covered or the number of cover units equals the number of base units + 2.
My units are numbered from 0 to 26 with 0 to 8 for the rows, 9 to 17 for the columns and 18 to 26 for the boxes.

Code:

MainFunction
{
  for digit = 0 to 8
  {
     Initialize templates (digit)

     AddBaseUnit (StartUnit = 0, BaseSet = Empty, CoverSets = Empty)
  }
}

AddBaseUnit (StartUnit, BaseSet, CoverSets)
{
  for i = StartUnit to 26
  {
    if Unit[i] contains candidates AND Unit[i] and BaseSet don't share candidates then
    {
      NewBaseSet = BaseSet + Unit[i]

      AddCoverUnit (ListOfBaseCandidates, CoverSets)

      if there are candidates not being part of BaseSet then
        AddBaseUnit (StartUnit = i + 1, NewBaseSet, CoverSets)
    }
  }
}

AddCoverUnit (ListOfBaseCandidates, CoverSet, DoubleCoverSet, TripleCoverSet)
{
  Take first base candidate from the list
  for i = Candidate->Cover1 to Candidate->Cover2   
  // This loop is worked twice for the possible cover units of the first candidate
  {
    NewCoverSet = CoverSet + Unit[i]
    NewDoubleCoverSet = DoubleCoverSet + (CoverSet AND Unit[i])
    NewTripleCoverSet = TripleCoverSet + (DoubleCoverSet AND Unit[i])   

    Remove all candidates belonging to Unit[i] from the list
    if the list is empty
    {
      if number of cover units = number of base units then
      {
        Eliminate all Candidates that belong to NewCoverSet but not BaseSet
        Eliminate all Candidates that belong to NewDoubleCoverSet
      }

      if number of cover units = number of base units + 1 then
        Eliminate all Candidates that belong to NewDoubleCoverSet but not BaseSet

      if number of cover units = number of base units + 2 then
        Eliminate all Candidates that belong to NewTripleCoverSet
    }
    else if number of cover units < number of base units + 2
      AddCoverUnit (ListOfBaseCandidates, NewCoverSet, NewDoubleCoverSet, NewTripleCoverSet)      
 
    Add the removed candidates again to the list
  }
}


I might add that I don't actually eliminate the candidates right away but just mark them to be eliminated.
This algorithm finds fish patterns of any dimension in one go, so in order to get a useful output beyond a simple list of candidates that can be eliminated, I will have to add some code to produce a list of patterns and sort it.
So far I just count the patterns the algorithm finds and it produces 120 different finned fish from swordfish to squirmbag for a puzzle with only one single elimination. Smile
Back to top
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 243
:

Items
PostPosted: Wed Jan 10, 2007 12:25 pm    Post subject: re: overlap in "base" Reply with quote

Obi-Wahn wrote:

    Thank you very much for your input.
    But as I see it, if you allow base units to overlap, the whole reasoning for eliminations doesn't work anymore. The point is that in order to fill N base units you need N different candidates, because the base units don't overlap.
    Since every base candidate also belongs to a cover unit, this fills at least N cover units. So if you only have less than N cover units covering all base candidates, the puzzle isn't solvable anymore. And that's why in a finless fish you can eliminate every candidate of the cover set that's outside the base set, because it removes a cover unit without removing a base unit. And you can eliminate every double covered candidate, because it removes 2 cover units but only 1 base unit.

    After reading your post again I'm beginning to think you are right. Since we look at the basic fish pattern after removing the candidates in the fin cells, two base units overlapping in a fin don't hurt the basic fish pattern. But I have no idea yet how to include this in my algorithm, since I don't handle fin candidates any different then normal base candidates.


    hi Obi-Wahn,

    first, forget about the fin -- how do you handle the finless fish with overlap in the "base" ? which is certainly possible in the Franken and Mutant fish -- the requirement is that any such overlap is known to not contain the digit -- you'll see those extra "/" cells in the diagrams --
Back to top
View user's profile Send private message
Obi-Wahn

Joined: 21 Aug 2006
Posts: 18
:

Items
PostPosted: Wed Jan 10, 2007 1:00 pm    Post subject: Reply with quote

Well that's easy. I have a template (bitmap) containing every candidate of the digit in question, a template of the candidates already added to the base set and a template for every unit that shows which cells belong to the unit.
Before I add a new unit to the base set I'm using the AND operation with the candidate and unit templates to get a template with all candidates in the new unit. Then I'm using another AND operation with this template and the template of the base set and check if the resulting template is empty.

BTW, here's the example I was talking about:
Code:

.---------------.---------------.---------------.
| 6    5    9   | 1    2    4   | 7    3    8   |
| 3    2    1   | 6    8    7   | 5    49   49  |
| 8    7    4   | 9    5    3   | 1    6    2   |
:---------------+---------------+---------------:
| 2    49   5   | 48   7    18  | 6    149  3   |
| 14   8    6   | 5    3    9   | 2    14   7   |
| 1479 349  37  | 2    146  16  | 8    5    49  |
:---------------+---------------+---------------:
| 49   6    2   | 7    49   5   | 3    8    1   |
| 45   134  38  | 48   146  2   | 9    7    56  |
| 579  19   78  | 3    169  168 | 4    2    56  |
'---------------'---------------'---------------'

 .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  .  4  4
 .  .  . |  .  .  . |  .  .  .
---------+----------+----------
 .  4  . |  4  .  . |  . -4  .
 4  .  . |  .  .  . |  .  4  .
 4  4  . |  .  4  . |  .  .  4
---------+----------+----------
 4  .  . |  .  4  . |  .  .  .
 4  4  . |  4  4  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .


My algorithm produces the following list of 120 patterns (I put different covers for the same base in one line):
Code:

r257c24/r4c8b3478    /r4b34678    /r4c8b3478   /r4c89b478
r257c2b5/r4c58b347   /r4c5b3467   /r4c58b347   /r4c589b47
r257c4/r4c18b38      /r4c1b368    /r4c18b38    /r4c189b8
r257b5/r4c158b3      /r4c15b36    /r4c158b3    /r4c1589
r25c24/r48c8b34      /r48b346     /r48c8b34    /r48c89b4
r25c2b58/r48c58b34   /r48c5b346   /r48c58b34   /r48c589b4
r25c4b7/r48c18b3     /r48c1b36    /r48c18b3    /r48c189
r25b578/r48c158b3    /r48c15b36   /r48c158b3   /r48c1589
r57c24/r4c8b478      /r4b4678
r57c249/r24c8b4678   /r4c8b34678  /r24b4678    /r4b34678
r57c24b3/r24c8b478   /r4c89b478   /r24b4678    /r24c8b4678   /r4c89b4678
r57c29b5/r24c58b467  /r4c58b3467  /r24c5b467   /r4c5b3467
r57c2b35/r24c58b47   /r4c589b47   /r24c5b467   /r24c58b467   /r4c589b467
r57c2b5/r4c58b47     /r4c5b467
r57c4/r4c18b8        /r4c1b68
r57c49/r24c18b68     /r4c18b368   /r24c1b68    /r4c1b368
r57c4b3/r24c18b8     /r4c189b8    /r24c1b68    /r24c18b68    /r4c189b68
r57c9b5/r24c158b6    /r4c158b36   /r24c15b6    /r4c15b36
r57b35/r24c158       /r4c1589     /r24c15b6    /r24c158b6    /r4c1589b6
r57b5/r4c158         /r4c15b6
r5c24/r48c8b4        /r48b46
r5c249/r248c8b46     /r48c8b346   /r248b46     /r48b346
r5c24b3/r248c8b4     /r48c89b4    /r248b46     /r248c8b46    /r48c89b46
r5c29b58/r248c58b46  /r48c58b346  /r248c5b46   /r48c5b346
r5c2b358/r248c58b4   /r48c589b4   /r248c5b46   /r248c58b46   /r48c589b46
r5c2b58/r48c58b4     /r48c5b46
r5c49b7/r248c18b6    /r48c18b36   /r248c1b6    /r48c1b36
r5c4b37/r248c18      /r48c189     /r248c1b6    /r248c18b6    /r48c189b6
r5c4b7/r48c18        /r48c1b6
r5c9b578/r248c158b6  /r48c158b36  /r248c15b6   /r48c15b36
r5b3578/r248c158     /r48c1589    /r248c15b6   /r248c158b6   /r48c1589b6
r5b578/r48c158       /r48c15b6


You have to keep in mind that every finned fish can be interpreted in at least two ways according to what is the fin, so the first example r257c24/r4c8b3478 actually means:
Code:

 .  .  . |  .  .  . |  .  .  .       .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  . *4 *4       .  .  . |  .  .  . |  . *4 *4 
 .  .  . |  .  .  . |  .  .  .       .  .  . |  .  .  . |  .  .  . 
---------+----------+----------     ---------+----------+----------
 . *4  . | #4  .  . |  . -4  .       . *4  . | *4  .  . |  . -4  .     
*4  .  . |  .  .  . |  . *4  .      *4  .  . |  .  .  . |  . #4  .
 4  4  . |  .  4  . |  .  .  4       4  4  . |  .  4  . |  .  .  4
---------+----------+----------     ---------+----------+----------
*4  .  . |  . *4  . |  .  .  .      *4  .  . |  . *4  . |  .  .  .
 4 *4  . | *4  4  . |  .  .  .       4 *4  . | *4  4  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .       .  .  . |  .  .  . |  .  .  .
 Sashimi Mutant Squirmbag            Sashimi Mutant Squirmbag
 r257c24/c8b3478 with fin r4c4       r257c24/r4b3478 with fin r5c8


Of course the simplest pattern would be a swordfish, e.g. r57b5/r4c158
Code:

 .  .  . |  .  .  . |  .  .  .       .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  .  4  4       .  .  . |  .  .  . |  .  4  4 
 .  .  . |  .  .  . |  .  .  .       .  .  . |  .  .  . |  .  .  . 
---------+----------+----------     ---------+----------+----------
 .  4  . | #4  .  . |  . -4  .       .  4  . | *4  .  . |  . -4  .     
*4  .  . |  .  .  . |  . *4  .      *4  .  . |  .  .  . |  . #4  .
 4  4  . |  . *4  . |  .  .  4       4  4  . |  . *4  . |  .  .  4
---------+----------+----------     ---------+----------+----------
*4  .  . |  . *4  . |  .  .  .      *4  .  . |  . *4  . |  .  .  .
 4  4  . |  4  4  . |  .  .  .       4  4  . |  4  4  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .       .  .  . |  .  .  . |  .  .  .
 Sashimi Franken Swordfish           Sashimi Mutant Swordfish
 r57b5/c158 with fin r4c4            r57b5/r4c15 with fin r5c8


@rkral: I like that you distinguish between finned and sashimi mutant fish, because that's something I was missing on the Ultimate FISH Guide.
Back to top
View user's profile Send private message
Myth Jellies

Joined: 20 Sep 2005
Posts: 14
:

Items
PostPosted: Thu Jan 11, 2007 5:16 am    Post subject: Reply with quote

You might want to check out my notes on handling internal intersections in NxN constraint group base sets about halfway into the post here.
_________________
Myth Jellies
Back to top
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Thu Jan 11, 2007 1:24 pm    Post subject: Reply with quote

Obi-Wahn wrote:
My algorithm produces the following list of 120 patterns (I put different covers for the same base in one line):
Code:

r257c24/r4c8b3478    /r4b34678    /r4c8b3478   /r4c89b478
(...)
r57b5/r4c158         /r4c15b6
(...)

To be clear, are you saying all 120 patterns exist for the same digit -- presumably digit 4 -- and for the same puzzle state Question And do they all yield an exclusion Question

If so, that's an amazing result!

Obi-Wahn, thanks for posting your pseudo-code. I hope to have some intelligent questions after studying it a bit. And would you please comment a bit about data structures relative to the code Question

rkral
Back to top
View user's profile Send private message
Obi-Wahn

Joined: 21 Aug 2006
Posts: 18
:

Items
PostPosted: Thu Jan 11, 2007 5:57 pm    Post subject: Reply with quote

rkral wrote:
To be clear, are you saying all 120 patterns exist for the same digit -- presumably digit 4 -- and for the same puzzle state Question And do they all yield an exclusion Question


Yes, it was the output for the pattern above the list, digit 4, all for the same puzzle state and yielding an exclusion.

However, I must admit that the list contains some duplicates because the cover set could be generated in different orders. It also contained many patterns that contained unnecessary cover units containing only base candidates that were already covered by other units.
Furthermore I realised that r2 and b3 contain exactly the same candidates, so these units can be treated as the same unit. I tweaked my program accordingly and the list was reduced to 32 patterns:

Code:

5: r257c24/r4c89b478
5: r257c2b5/r4c589b47
4: r257c4/r4c189b8
4: r257b5/r4c1589
4: r25c24/r48c89b4
5: r25c2b58/r48c589b4
4: r25c4b7/r48c189
5: r25b578/r48c1589
4: r57c24/r4c8b478          /r4b4678
5: r57c249/r24b4678
5: r57c29b5/r24c5b467
4: r57c2b5/r4c58b47         /r4c5b467
3: r57c4/r4c18b8            /r4c1b68
4: r57c49/r24c1b68
4: r57c9b5/r24c15b6
3: r57b5/r4c158             /r4c15b6
3: r5c24/r48c8b4            /r48b46
4: r5c249/r248b46
5: r5c29b58/r248c5b46
4: r5c2b58/r48c58b4         /r48c5b46
4: r5c49b7/r248c1b6
3: r5c4b7/r48c18            /r48c1b6
5: r5c9b578/r248c15b6
4: r5b578/r48c158           /r48c15b6

r2 can be replaced by b3


Here's a list of the Sashimi Swordfish Patterns only in the common format:
Code:

 .  .  . |  .  .  . |  .  .  .       .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  .  4  4       .  .  . |  .  .  . |  .  4  4 
 .  .  . |  .  .  . |  .  .  .       .  .  . |  .  .  . |  .  .  . 
---------+----------+----------     ---------+----------+----------
 .  4  . | #4  .  . |  . -4  .       .  4  . | *4  .  . |  . -4  .     
*4  .  . |  .  .  . |  . *4  .      *4  .  . |  .  .  . |  . #4  .
 4  4  . |  .  4  . |  .  .  4       4  4  . |  .  4  . |  .  .  4
---------+----------+----------     ---------+----------+----------
*4  .  . |  . *4  . |  .  .  .      *4  .  . |  . *4  . |  .  .  .
 4  4  . | *4  4  . |  .  .  .       4  4  . | *4  4  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .       .  .  . |  .  .  . |  .  .  .
 Sashimi Mutant Swordfish           Sashimi Mutant Swordfish
 r57c4/c18b8 with fin r4c4           r57c4/r4c1b8 with fin r5c8

 .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  .  4  4 
 .  .  . |  .  .  . |  .  .  .
---------+----------+----------
 .  4  . | #4  .  . |  . -4  .     
*4  .  . |  .  .  . |  . *4  .
 4  4  . |  .  4  . |  .  .  4
---------+----------+----------
*4  .  . |  . *4  . |  .  .  .
 4  4  . | *4  4  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .
 Sashimi Mutant Swordfish     
 r57c4/c1b68 with fin r4c4     

 .  .  . |  .  .  . |  .  .  .       .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  .  4  4       .  .  . |  .  .  . |  .  4  4 
 .  .  . |  .  .  . |  .  .  .       .  .  . |  .  .  . |  .  .  . 
---------+----------+----------     ---------+----------+----------
 .  4  . | #4  .  . |  . -4  .       .  4  . | *4  .  . |  . -4  .     
*4  .  . |  .  .  . |  . *4  .      *4  .  . |  .  .  . |  . #4  .
 4  4  . |  . *4  . |  .  .  4       4  4  . |  . *4  . |  .  .  4
---------+----------+----------     ---------+----------+----------
*4  .  . |  . *4  . |  .  .  .      *4  .  . |  . *4  . |  .  .  .
 4  4  . |  4  4  . |  .  .  .       4  4  . |  4  4  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .       .  .  . |  .  .  . |  .  .  .
 Sashimi Franken Swordfish           Sashimi Mutant Swordfish
 r57b5/c158 with fin r4c4            r57b5/r4c15 with fin r5c8

 .  .  . |  .  .  . |  .  .  . 
 .  .  . |  .  .  . |  .  4  4
 .  .  . |  .  .  . |  .  .  .
---------+----------+----------
 .  4  . | #4  .  . |  . -4  .     
*4  .  . |  .  .  . |  . *4  .
 4  4  . |  . *4  . |  .  .  4
---------+----------+----------
*4  .  . |  . *4  . |  .  .  .
 4  4  . |  4  4  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .
 Sashimi Franken Swordfish     
 r57b5/c15b6 with fin r4c4     

 .  .  . |  .  .  . |  .  .  .       .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  .  4  4       .  .  . |  .  .  . |  .  4  4 
 .  .  . |  .  .  . |  .  .  .       .  .  . |  .  .  . |  .  .  . 
---------+----------+----------     ---------+----------+----------
 . *4  . | #4  .  . |  . -4  .       . *4  . | *4  .  . |  . -4  .     
*4  .  . |  .  .  . |  . *4  .      *4  .  . |  .  .  . |  . #4  .
 4 *4  . |  .  4  . |  .  .  4       4 *4  . |  .  4  . |  .  .  4
---------+----------+----------     ---------+----------+----------
 4  .  . |  .  4  . |  .  .  .       4  .  . |  .  4  . |  .  .  .
 4 *4  . | *4  4  . |  .  .  .       4 *4  . | *4  4  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .       .  .  . |  .  .  . |  .  .  .
 Sashimi Mutant Swordfish            Sashimi Mutant Swordfish
 r5c24/r8c8b4 with fin r4c4          r5c24/r48b4 with fin r5c8

 .  .  . |  .  .  . |  .  .  . 
 .  .  . |  .  .  . |  .  4  4
 .  .  . |  .  .  . |  .  .  .
---------+----------+----------
 . *4  . | #4  .  . |  . -4  .     
*4  .  . |  .  .  . |  . *4  .
 4 *4  . |  .  4  . |  .  .  4
---------+----------+----------
 4  .  . |  .  4  . |  .  .  .
 4 *4  . | *4  4  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .
 Sashimi Mutant Swordfish     
 r5c24/r8b46 with fin r4c4     

 .  .  . |  .  .  . |  .  .  .       .  .  . |  .  .  . |  .  .  .
 .  .  . |  .  .  . |  .  4  4       .  .  . |  .  .  . |  .  4  4 
 .  .  . |  .  .  . |  .  .  .       .  .  . |  .  .  . |  .  .  . 
---------+----------+----------     ---------+----------+----------
 .  4  . | #4  .  . |  . -4  .       . *4  . | *4  .  . |  . -4  .     
*4  .  . |  .  .  . |  . *4  .      *4  .  . |  .  .  . |  . #4  .
 4  4  . |  .  4  . |  .  .  4       4 *4  . |  .  4  . |  .  .  4
---------+----------+----------     ---------+----------+----------
*4  .  . |  .  4  . |  .  .  .      *4  .  . |  .  4  . |  .  .  .
*4 *4  . | *4  4  . |  .  .  .      *4 *4  . | *4  4  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .       .  .  . |  .  .  . |  .  .  .
 Sashimi Mutant Swordfish            Sashimi Mutant Swordfish
 r5c4b7/r8c18 with fin r4c4          r5c4b7/r48c1 with fin r5c8

 .  .  . |  .  .  . |  .  .  . 
 .  .  . |  .  .  . |  .  4  4
 .  .  . |  .  .  . |  .  .  .
---------+----------+----------
 .  4  . | #4  .  . |  . -4  .     
*4  .  . |  .  .  . |  . *4  .
 4  4  . |  .  4  . |  .  .  4
---------+----------+----------
*4  .  . |  .  4  . |  .  .  .
*4 *4  . | *4  4  . |  .  .  .
 .  .  . |  .  .  . |  .  .  .
 Sashimi Mutant Swordfish     
 r5c4b7/r8c1b6 with fin r4c4     

All those patterns have one of two possible fins and lead to the same exclusion, but they use different sets of base and cover units.
Back to top
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Thu Jan 11, 2007 6:54 pm    Post subject: Reply with quote

Obi-Wahn, that's some really good stuff. I think you've got the penultimate fishing algorithm for Ultimate Fish. Just add the capability to handle candiates in the intersection of base units ... and then you'll have the ultimate fishing algorithm.

Not only does your algorithm use logic instead of elimination-by-contradiction, it can output a deduction in logical terms.

Obi-Wahn wrote:
rkral wrote:
To be clear, are you saying all 120 patterns exist for the same digit -- presumably digit 4 -- and for the same puzzle state Question And do they all yield an exclusion Question


Yes, it was the output for the pattern above the list, digit 4, all for the same puzzle state and yielding an exclusion.

By an exclusion, I presume you mean the same exclusion in this case. Correct?
Back to top
View user's profile Send private message
Obi-Wahn

Joined: 21 Aug 2006
Posts: 18
:

Items
PostPosted: Fri Jan 12, 2007 10:43 pm    Post subject: Reply with quote

rkral wrote:
By an exclusion, I presume you mean the same exclusion in this case. Correct?

That's affirm. Smile

I am now implementing overlapping base units. At first I feared, that this would produce many times as many different base sets and thus would slow down my program beyond useful application.
But thinking about what kind of overlapping should be allowed, I came up with the following idea: if two overlapping base units share the same candidate, then there's only one unit left for this candidate as cover unit. And since this candidate must be a fin and every exclusion candidate must share a unit with all fin cells, only candidates within this remaining unit can be excluded. If now two overlapping base units would share more then one candidate (e.g. a row and a box), the remaining cover units for these candidates would be two different units of the same type (columns in this case). But since different units of the same type can never overlap, they can't share the same exclusion candidate and thus can never lead to an exclusion.
So for a first try I allowed overlapping only once and only with a single shared candidate. In fact this didn't slow down my program on my benchmark puzzle at all, because there simply weren't any units that did overlap only in one candidate. Smile

For the previously unsolvable puzzle I posted, my program now finds the 3 elimination candidates within seconds and comes up with the following list of patterns:

Code:

@2Fins 6: r348c159/r69c38b2357
@2Fins 5: r348c19/r69c368b37
@2Fins 6: r348c359/r69c18b2345
@2Fins 5: r348c39/r69c168b34
@2Fins 6: r348c59b4/r69c38b2357
@2Fins 6: r348c59b7/r69c18b2345
@2Fins 5: r348c9b4/r69c368b37
@2Fins 5: r348c9b7/r69c168b34
@2Fins 6: r349c159/r68c38b2359
@2Fins 6: r349c15b6/r68c378b259
@2Fins 5: r349c19/r68c368b39
@2Fins 5: r349c1b6/r68c3678b9
@2Fins 6: r34c159b7/r68c38b2359
@2Fins 6: r34c159b9/r69c38b2357
@2Fins 5: r34c19b7/r68c368b39
@2Fins 5: r34c19b9/r69c368b37
@2Fins 6: r38c359b6/r569c18b234
@2Fins 6: r38c39b56/r569c168b34
@2Fins 5: r48c159/r269c38b57
@2Fins 5: r48c19b2/r269c368b7
@2Fins 5: r48c359/r269c18b45
@2Fins 5: r48c39b2/r269c168b4
@2Fins 5: r48c59b4/r269c38b57
@2Fins 5: r48c59b7/r269c18b45
@2Fins 5: r48c9b24/r269c368b7
@2Fins 5: r48c9b27/r269c168b4
@2Fins 5: r49c159/r268c38b59
@2Fins 6: r49c15b36/r268c378b59
@2Fins 5: r49c19b2/r268c368b9
@2Fins 6: r49c1b236/r268c3678b9
@2Fins 5: r4c159b7/r268c38b59
@2Fins 5: r4c159b9/r269c38b57
@2Fins 5: r4c19b27/r268c368b9
@2Fins 5: r4c19b29/r269c368b7
@2Fins 5: r8c359b6/r2569c18b4
@2Fins 6: r8c39b256/r2569c168b4


The @ I used to mark overlapping base units and 2Fins means, that there are fin cells in 2 different units.
The 6th last line is rkral's solution with r8 and b9 as additional units covering the fins. I still don't know how you came up with this without a computer...

However I'm aware that although any two base units may overlap in one candidate only, it's still possible that another two base units overlap in another candidate as long as these candidates share the same cover unit or even 2 cover units if they overlap in at least one exclusion candidate.

And so unfortunately there are 3 more template solvable puzzles that do still escape my fishing algorithm (NoFish2 is the one now solved):

Code:

NoFish1
.---------------.---------------.---------------.
| 137  78   1347| 4679 689  149 | 16   5    2   |
| 9    578  2   | 567  568  15  | 16   3    4   |
| 145  6    145 | 3    25   1245| 9    8    7   |
:---------------+---------------+---------------:
| 247  1    479 | 49   29   8   | 5    6    3   |
| 245  245  6   | 1    3    245 | 8    7    9   |
| 8    3    59  | 569  569  7   | 4    2    1   |
:---------------+---------------+---------------:
| 245  2459 8   | 59   1    3   | 7    49   6   |
| 6    579  57  | 2    4    59  | 3    1    8   |
| 13   49   13  | 8    7    6   | 2    49   5   |
'---------------'---------------'---------------'

  .  .  . |  .  .  . |  .  .  .
  .  5  . |  5  5  5 |  .  .  .
  5  .  5 |  . -5  5 |  .  .  .
----------+----------+----------
  .  .  . |  .  .  . |  .  .  .
  5  5  . |  .  .  5 |  .  .  .
  .  .  5 |  5  5  . |  .  .  . 
----------+----------+----------
  5  5  . |  5  .  . |  .  .  .
  .  5  5 |  .  .  5 |  .  .  .
  .  .  . |  .  .  . |  .  .  .


NoFish3
.---------------.---------------.---------------.
| 2    6    5   | 34   1489 1389| 49   7    189 |
| 1    7    89  | 2    489  5   | 349  6    389 |
| 89   4    3   | 7    6    189 | 2    5    189 |
:---------------+---------------+---------------:
| 7    189  6   | 34   1489 2   | 139  48   5   |
| 3    2    489 | 5    7    189 | 19   48   6   |
| 5    189  489 | 6    1489 1389| 7    2    39  |
:---------------+---------------+---------------:
| 4    5    1   | 8    3    7   | 6    9    2   |
| 6    3    2   | 9    5    4   | 8    1    7   |
| 89   89   7   | 1    2    6   | 5    3    4   |
'---------------'---------------'---------------'

  .  .  . |  .  9  9 | -9  .  9
  .  .  9 |  .  9  . |  9  .  9
  9  .  . |  .  .  9 |  .  .  9
----------+----------+----------
  .  9  . |  .  9  . |  9  .  .
  .  .  9 |  .  .  9 |  9  .  .
  .  9  9 |  .  9  9 |  .  .  9 
----------+----------+----------
  .  .  . |  .  .  . |  .  .  .
  .  .  . |  .  .  . |  .  .  .
  9  9  . |  .  .  . |  .  .  .


NoFish4
.------------------.------------------.------------------.
| 8     5     49   | 6     2     3    | 49    7     1    |
| 2     479   479  | 49    1     8    | 3     6     5    |
| 1     3     6    | 49    7     5    | 8     2     49   |
:------------------+------------------+------------------:
| 57    179   2    | 3     8     4    | 59    19    6    |
| 3     148   458  | 2     6     9    | 45    148   7    |
| 49    6     489  | 1     5     7    | 2     489   3    |
:------------------+------------------+------------------:
| 49    2     1    | 5     49    6    | 7     3     8    |
| 57    479   34579| 8     349   1    | 6     49    2    |
| 6     489   38   | 7     349   2    | 1     5     49   |
'------------------'------------------'------------------'

  .  .  4 |  .  .  . |  4  .  .
  .  4  4 |  4  .  . |  .  .  .
  .  .  . |  4  .  . |  .  .  4
----------+----------+----------
  .  .  . |  .  .  . |  .  .  .
  .  4  4 |  .  .  . |  4  4  .
  4  .  4 |  .  .  . |  .  4  . 
----------+----------+----------
  4  .  . |  .  4  . |  .  .  .
  .  4  4 |  .  4  . |  .  4  .
  .  4  . |  . -4  . |  .  .  4

  .  .  9 |  .  .  . |  9  .  .
  .  9  9 |  9  .  . |  .  .  .
  .  .  . |  9  .  . |  .  .  9
----------+----------+----------
  .  9  . |  .  .  . |  9  9  .
  .  .  . |  .  .  . |  .  .  .
  9  .  9 |  .  .  . |  .  9  . 
----------+----------+----------
  9  .  . |  .  9  . |  .  .  .
  .  9  9 |  .  9  . |  .  9  .
  .  9  . |  . -9  . |  .  .  9

Maybe you can impress me once again, rkral?

[edit]After changing the algorithm to allow multiple overlaps in a single fin unit, it now solves NoFish4, although there's only one shared candidate. There must have been some bug in my first attempt:

Code:

  .  . *4 |  .  .  . | *4  .  .
  .  4  4 |  4  .  . |  .  .  .
  .  .  . |  4  .  . |  .  . *4
----------+----------+----------
  .  .  . |  .  .  . |  .  .  .
  .  4  4 |  .  .  . |  4  4  .
 *4  . *4 |  .  .  . |  . *4  . 
----------+----------+----------
 *4  .  . |  . *4  . |  .  .  .
  .  4  4 |  .  4  . |  . *4  .
  .  4  . |  . -4  . |  .  . #4
 Sashimi Mutant Squirmbag r167c9b9/c1358b3 with fin r9c9.

The same pattern works for digit 9. That's 2 down, 2 to go.[/edit]
Back to top
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Sat Jan 13, 2007 7:27 pm    Post subject: Reply with quote

Obi-Wahn wrote:
Code:

NoFish1
  .  .  . |  .  .  . |  .  .  .
  .  5  . |  5  5  5 |  .  .  .
  5  .  5 |  . -5  5 |  .  .  .
----------+----------+----------
  .  .  . |  .  .  . |  .  .  .
  5  5  . |  .  .  5 |  .  .  .
  .  .  5 |  5  5  . |  .  .  . 
----------+----------+----------
  5  5  . |  5  .  . |  .  .  .
  .  5  5 |  .  .  5 |  .  .  .
  .  .  . |  .  .  . |  .  .  .

If you can test this easily, does your algorithm find the exclusion if the candidate at r8c2 didn't exist?
Quote:
Code:

NoFish3
  .  .  . |  .  9  9 | -9  .  9
  .  .  9 |  .  9  . |  9  .  9
  9  .  . |  .  .  9 |  .  .  9
----------+----------+----------
  .  9  . |  .  9  . |  9  .  .
  .  .  9 |  .  .  9 |  9  .  .
  .  9  9 |  .  9  9 |  .  .  9 
----------+----------+----------
  .  .  . |  .  .  . |  .  .  .
  .  .  . |  .  .  . |  .  .  .
  9  9  . |  .  .  . |  .  .  . 

And the same here, if the candidates at r6c3 and r6c6 didn't exist?
Back to top
View user's profile Send private message
Obi-Wahn

Joined: 21 Aug 2006
Posts: 18
:

Items
PostPosted: Sat Jan 13, 2007 9:18 pm    Post subject: Reply with quote

Not exactly. For NoFish1 without r8c2 it finds eliminations for r6c3 and r5c6. For example:
Code:

NoFish1
  .  .  . |  .  .  . |  .  .  .
  .  5  . |  5  5  5 |  .  .  .
  5  .  5 |  .  5  5 |  .  .  .
----------+----------+----------
  .  .  . |  .  .  . |  .  .  .
 #5 #5  . |  .  . *5 |  .  .  .
  .  . -5 |  5  5  . |  .  .  . 
----------+----------+----------
  5  5  . |  5  .  . |  .  .  .
  .  . *5 |  .  . *5 |  .  .  .
  .  .  . |  .  .  . |  .  .  .
 Sashimi X-Wing r58/c36 with fins r5c12

For NoFish3 without r6c3 and r6c6 it finds an elimination on r2c5:
Code:

NoFish3
  .  .  . |  .  9  9 |  9  .  9
  .  . *9 |  . -9  . |  9  .  9
  9  .  . |  .  .  9 |  .  .  9
----------+----------+----------
  .  9  . |  . #9  . |  9  .  .
  .  . *9 |  .  . *9 |  9  .  .
  .  9    |  . #9    |  .  .  9 
----------+----------+----------
  .  .  . |  .  .  . |  .  .  .
  .  .  . |  .  .  . |  .  .  .
  9  9  . |  .  .  . |  .  .  . 
 Sashimi Franken X-Wing c3b5/r25 with fins r46c5

But I saw that I made a mistake in restricting the fin covering units for these cases to 2. Actually there can be even 3 units as long as they share one common candidate. I just have to make sure that there is at least one potential elimination candidate left not being a fin due to overlaping base units.
My program came up with base sets like r123c123 where all shared candidates belong to the same cover unit b1 but unfortunately leaving no candidate in this unit when the fins are removed, making the puzzle unsolvable.

[edit] I completed my program now, but it still finds no Fish in the above patterns. Furthermore after filtering 100000 randomly generated puzzles here's another template solvable one that I can't find a fish pattern for:
Code:

NoFish5
.---------------.---------------.---------------.
| 1236 179  4   | 369  3679 8   | 29   67   5   |
| 36   789  5   | 2    4    39  | 1    67   89  |
| 26   789  29  | 5    679  1   | 3    4    289 |
:---------------+---------------+---------------:
| 9    2    3   | 4    1    7   | 8    5    6   |
| 4    6    8   | 39   239  5   | 7    1    29  |
| 7    5    1   | 68   68   29  | 4    29   3   |
:---------------+---------------+---------------:
| 8    3    6   | 7    5    4   | 29   29   1   |
| 12   4    29  | 1389 389  6   | 5    38   7   |
| 5    19   7   | 1389 2389 239 | 6    38   4   |
'---------------'---------------'---------------'

  .  9  . |  9  9  . |  9  .  .
  .  9  . |  .  .  9 |  .  .  9
  .  9 -9 |  .  9  . |  .  .  9
----------+----------+----------
  .  .  . |  .  .  . |  .  .  .
  .  .  . |  9  9  . |  .  .  9
  .  .  . |  .  .  9 |  .  9  . 
----------+----------+----------
  .  .  . |  .  .  . |  9  9  .
  .  .  9 | -9 -9  . |  .  .  .
  . -9  . |  9  9  9 |  .  .  . 

[edit] typo corrected. Thanks, daj95376. [/edit]
All three examples have in common, that if you try to set one of the exclusion candidates, it still needs coloring to find the contradiction in the pattern rather than just hidden singles.
Maybe these patterns really can't be expressed by any fish ...


Last edited by Obi-Wahn on Sun Jan 14, 2007 2:27 pm; edited 1 time in total
Back to top
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Sun Jan 14, 2007 1:38 am    Post subject: Reply with quote

Obi-Wahn wrote:
But I saw that I made a mistake in restricting the fin covering units for these cases to 2. Actually there can be even 3 units as long as they share one common candidate.

I haven't seen one of those yet, but would love to.

Obi-Wahn wrote:
Not exactly. For NoFish1 without r8c2 it finds eliminations for r6c3 and r5c6.
(...)
For NoFish3 without r6c3 and r6c6 it finds an elimination on r2c5:

Sorry, it was obviously not not one of my brighter ideas. Sad

I don't see a Fish equivalent for those Template exclusions, but an extension to Rod Hagglund's Broken Wing technique will work.

Code:

NoFish1
  .  .  . |  .  .  . |  .  .  .
  .  5  . | G5  5  5 |  .  .  .
  5  . G5 |  . -5  5 |  .  .  .
----------+----------+----------
  .  .  . |  .  .  . |  .  .  .
  5  5  . |  .  .  5 |  .  .  .
  .  . *5 | *5 G5  . |  .  .  . 
----------+----------+----------
  5  5  . | *5  .  . |  .  .  .
  . G5 *5 |  .  . *5 |  .  .  .
  .  .  . |  .  .  . |  .  .  .

If all the guardian cells ('G') were false, we would have a turbot fish ('*') with five conjugate links -- an impossibility. Hence at least one of the guardian cells must be true. Except for r8c2, r3c5 directly sees all the guardians. But r3c5 indirectly sees r8c2 via the grouped conjugate link in r2. Therefore r3c5<>5.

Code:

Nofish3
  .  .  . |  . G9 G9 | -9  .  9
  .  . *9 |  . *9  . | G9  . G9
  9  .  . |  .  . *9 |  .  .  9
----------+----------+----------
  .  9  . |  .  9  . |  9  .  .
  .  . *9 |  .  . *9 | G9  .  .
  .  9 G9 |  .  9 G9 |  .  .  9 
----------+----------+----------
  .  .  . |  .  .  . |  .  .  .
  .  .  . |  .  .  . |  .  .  .
  9  9  . |  .  .  . |  .  .  .

If all the guardian cells ('G')were false, we would have a turbot fish ('*')with five conjugate links -- an impossibility. Hence, at least one of the guardian cells must be true. Except for r6c36, r1c7 sees all the guardians. But r1c7 indirectly sees r6c36 via the grouped conjugate link in [edit: c9]. Therefore r1c7<>9.

Code:

NoFish5
 .  9  . |  9  9  . |  9  .  .
 . G9  . |  .  . *9 |  .  . *9
 .  9 -9 |  .  9  . |  .  . G9
---------+----------+----------
 .  .  . |  .  .  . |  .  .  .
 .  .  . |  9  9  . |  .  . *9
 .  .  . |  .  . *9 |  . *9  .
---------+----------+----------
 .  .  . |  .  .  . |  9  9  .
 .  .  9 |  9  9  . |  .  .  .
 .  9  . |  9  9 G9 |  .  .  .

If all the guardian cells ('G') were false, we would have a turbot fish ('*') with five conjugate links -- an impossibility. Hence, at least one of the guardian cells must be true. Except for r9c6, r3c3 sees all the guardians. But r3c3 indirectly sees r9c6 via the grouped conjugate link in r8. Therefore r3c3<>9.

[edit: added NoFish5 and changed to 'guardian' terms to avoid confusion with fish 'fins']


Last edited by rkral on Thu Jan 18, 2007 5:31 pm; edited 2 times in total
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 431
:

Items
PostPosted: Sun Jan 14, 2007 2:52 am    Post subject: Reply with quote

Obi-Wahn wrote:

[edit] I completed my program now, but it still finds no Fish in the above patterns. Furthermore after filtering 100000 randomly generated puzzles here's another template solvable one that I can't find a fish pattern for:

Code:
NoFish5
.---------------.---------------.---------------.
| 1236 179  4   | 369  3679 8   | 29   67   5   |
| 36   789  5   | 2    4    39  | 1    67   89  |
| 26   789  29  | 5    679  1   | 3    4    289 |
:---------------+---------------+---------------:
| 9    2    3   | 4    1    7   | 8    5    6   |
| 4    6    8   | 39   239  5   | 7    1    29  |
| 7    5    1   | 68   68   29  | 4    29   3   |
:---------------+---------------+---------------:
| 8    3    6   | 7    5    4   | 29   29   1   |
| 12   4    29  | 1389 389  6   | 5    38   7   |
| 5    19   7   | 1389 2389 239 | 6    38   4   |
'---------------'---------------'---------------'

  .  9  . |  9  9  . |  9  .  .
  .  9  . |  .  .  9 |  .  .  9
  .  9 -9 |  .  9  . |  .  .  9
----------+----------+----------
  .  .  . |  .  .  . |  .  .  .
  .  .  . |  9  9  . |  .  .  9
  .  .  . |  .  .  9 |  .  .  9 
----------+----------+----------
  .  .  . |  .  .  . |  9  9  .
  .  .  9 | -9 -9  . |  .  .  .
  . -9  . |  9  9  9 |  .  .  . 

The trouble with Template eliminations is that they cascade and/or are really assignments. In this case, both situations are true. What you have is [r8c3]=9 being the necessary assignment to make all of your eliminations work. In order to do this, you need to eliminate one of the three binding constraints against the assignment ... and the remaining eliminations will 'cascade' from it.

Find a fish that sets [r8c45]<>9, then [r8c3]=9 follows and forces the two remaining eliminations. (hint: removed)

[Edit: Thanks rkral for pointing me to the correct box for a finned franken Swordfish. I can't find mutant fish and most of the time I pick the wrong box for franken fish. However, I'm deadly on exo/remote fish ... and I know there's a finned exo/remote Swordfish r159\c245.]


Last edited by daj95376 on Sun Jan 14, 2007 1:55 pm; edited 1 time in total
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Goto page 1, 2, 3, 4, 5, 6, 7, 8  Next
Page 1 of 8

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron
FREE FORUM HOSTING by AtFreeForum. Terms of Service - Privacy Policy
FASHION ACCESSORIES - BLING BLING - LADIES WATCHES - KOREAN CHILDREN CLOTHING - ONLINE BARGAIN STORE - FASHION JEWELLERIES