SudoCue Users Forum Index SudoCue Users
A forum for users of the SudoCue programs and the services of SudoCue.Net
 
 FAQFAQ   SearchSearch   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Aren't the "template" and "nishio" the s

 
Post new topic   Reply to topic    SudoCue Users Forum Index -> Solving Techniques & Tips
View previous topic :: View next topic  
Author Message
David Bryant
Gold Member
Gold Member


Joined: 20 Jan 2006
Posts: 86
Location: Denver, Colorado

PostPosted: Tue Mar 21, 2006 12:19 am    Post subject: Aren't the "template" and "nishio" the s Reply with quote

In working some of Ruud’s puzzles I’ve learned to know and love the “template” pattern. Here’s an example, from the first puzzle (13 Dec, 2005) published on this site.
Code:
  7     6     1     8     3     2     4     9     5
  4     9     8     1     6     5     2    37    37
  3     5     2     4     9     7     6     1     8
  9   3478*  367x  36*   48     1    378*   5     2
 58    348*  356    2     7     9     1   3468   36
  2     1    367x  356*  458   68    378* 34678   9
  1    37*    9    567   58    68    357*   2     4
 568    2   3567   57     1     4     9   3678   367
 568   78     4     9     2     3    578   678    1

Observe the pattern of the "3"s in columns 2, 4, & 7. I've marked these spots with "*"s above. They form a "template" pattern, which works sort of like a swordfish.

A. r4c7 = 3 ==> r6c4 = 3 ==> r4c3 <> 3 & r6c3 <> 3
B. r6c7 = 3 ==> r4c4 = 3 ==> r4c3 <> 3 & r6c3 <> 3
C. r7c7 = 3 ==> r7c2 <> 3 ==> 3 in r4c2 or r5c2 ==> r4c3 <> 3 & r6c3 <> 3

So we can eliminate the “3” at r4c3 & r6c3, creating the {6, 7} pair in column 3. Neat!

Here’s my question. Why is this called a "template" pattern? There’s an older name for this -- it’s called "Nishio." Observe that the logic is exactly the same, but backwards.

Code:
  7     6     1     8     3     2     4     9     5
  4     9     8     1     6     5     2    37    37
  3     5     2     4     9     7     6     1     8
  9   3478   367a  36b   48     1    378*   5     2
 58    348   356    2     7     9     1   3468   36
  2     1    367b  356a  458   68    378* 34678   9
  1    37ab   9    567   58    68    357*   2     4
 568    2   3567   57     1     4     9   3678   367
 568   78     4     9     2     3    578   678    1


A. r4c3 = 3 ==> r7c2 = 3 ==> r6c4 = 3 ==> no way to fit a "3" in column 7.
B. r6c3 = 3 ==> r7c2 = 3 & r6c4 = 3 ==> no way to fit a "3" in column 7.

This second way of looking at it is a classic Nishio. So why are you calling this thing a "template" and not "Nishio", Ruud?
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Ruud
Site Owner
Site Owner


Joined: 30 Dec 2005
Posts: 601

PostPosted: Tue Mar 21, 2006 1:19 am    Post subject: Reply with quote

Hi David, good question.

I can tell you why this is happening.

When I created my solver program, SudoCue, I wanted to add some methods that could act as a "catch all" method following the logical methods.

At the back end, I have a Dancing Links algorithm, that will complete any Sudoku that cannot be solved by logic.

Just before Dancing Links, I have implemented the Trebor's Tables method, which was first introduced in Sudoku Susser. It is now more commonly known as the Forcing Net, Bifurcation, or Ariadne's Thread.

I then added a method that could catch all eliminations considering a single digit. This method would precede the Tables method, as it could be easier executed by hand, using the candidate patterns with colors. The method generates all 46656 possible templates for the distribution of a single digit. When a digit is placed or solved, all templates NOT containing a digit in this cell are removed from the set. When a candidate is eliminated, all templates containing the digit at that position are removed.

Finally, all remaining templates are OR'ed to produce a final template that contains all possible locations for the digit.

As I built more advanced techniques in my solver, template eliminations became rare. In fact, so rare that they now mostly shadow Nishio eliminations.

I still call them template eliminations, because that is what happens in my solver, and that is what I use to rate my sudoku collection.

I hope this sufficiently answered your question.

Kind regards,

Ruud.
Back to top
View user's profile Send private message Send e-mail
David Bryant
Gold Member
Gold Member


Joined: 20 Jan 2006
Posts: 86
Location: Denver, Colorado

PostPosted: Tue Mar 21, 2006 12:37 pm    Post subject: Great answer, Ruud! Reply with quote

That's a great answer, Ruud. Thank you! dcb Very Happy
Back to top
View user's profile Send private message Send e-mail Visit poster's website
David Bryant
Gold Member
Gold Member


Joined: 20 Jan 2006
Posts: 86
Location: Denver, Colorado

PostPosted: Mon Mar 27, 2006 6:13 pm    Post subject: More on templates -- and "coloring" Reply with quote

The 27 March, 2006 "Nightmare" contains an instructive instance of the "template" elimination.

After making a few fairly obvious moves I arrived at this position.
Code:
 489    7   12589 1589    6   1289+  459   249    3
 469  12469 1259    3   1257  1279    8   24679  256
  3    269  2589- 5789  2578    4   5679    1    256
  1    34     7     2    34     5    69    69     8
  5     8     6    179   17    179    2     3     4
 49   2349   239   48    348    6     1     5     7
 78     5    138    6   12478 1278-  347   247    9
7869+  169    4   1578  12578   3    567   267  1256
  2    136   13   1457    9    17   34567   8    156

Here we find a "template" elimination based on the fact that there are only two ways to place an "8" in column 6.

-- If r1c6 = 8 then r1c3 = 8 (only place left for an "8" in top left 3x3 box).
-- If r7c6 = 8 then r8c1 = 8 (only place left for an "8" in bottom left 3x3 box).
-- In each case there cannot be an "8" at r1c1, nor at r7c3.

Interestingly, we can visualize this "template" elimination as an application of the "coloring" method, as indicated by the +/- signs in the grid above. It's also pretty easy to translate this into the language of Nishio:

r1c1 = 8 ==> r7c6 = 8 ==> no way to fit an "8" in bottom left 3x3 box.
r6c3 = 8 ==> r1c6 = 8 ==> no way to fit an "8" in top left 3x3 box.

Oh, yeah -- after I'd solved this puzzle (a bit farther along I found an "8-star constellation" that cracked it wide open) I went back and ran SudoCue on it just for grins. Sure enough, the program calls this logic step a "template" elimination. dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Myth Jellies
Hooked
Hooked


Joined: 04 Apr 2006
Posts: 42

PostPosted: Thu Apr 13, 2006 4:25 am    Post subject: Re: Aren't the "template" and "nishio" t Reply with quote

David Bryant wrote:

Code:
  7     6     1     8     3     2     4     9     5
  4     9     8     1     6     5     2    37    37
  3     5     2     4     9     7     6     1     8
  9   3478*  367x  36*   48     1    378*   5     2
 58    348*  356    2     7     9     1   3468   36
  2     1    367x  356*  458   68    378* 34678   9
  1    37*    9    567   58    68    357*   2     4
 568    2   3567   57     1     4     9   3678   367
 568   78     4     9     2     3    578   678    1

Observe the pattern of the "3"s in columns 2, 4, & 7. I've marked these spots with "*"s above. They form a "template" pattern, which works sort of like a swordfish.


It actually IS a known entity called the finned swordfish, as shown below...
Code:
  7     6     1   |  8     3     2  |  4     9     5
  4     9     8   |  1     6     5  |  2    37    37
  3     5     2   |  4     9     7  |  6     1     8
 -----------------+-----------------+-----------------
 -9  *3478  -367  |*36    48     1  |*378    5     2
 58   #348   356  |  2     7     9  |  1   3468   36
 -2    *1   -367  |*356   458   68  |*378  34678   9
 -----------------+-----------------+-----------------
  1   *37     9   |*567   58    68  |*357    2     4
 568    2   3567  | 57     1     4  |  9   3678   367
 568   78     4   |  9     2     3  | 578   678    1

...The finned swordfish in r467c247 (fin in r5c2) kills any 3's in cells marked with a '-'. The "fin" prevents swordfish reductions in cells outside of the box containing the fin, but it can have no effect on the reductions that occur in the same box as the fin. Another way of looking at it is; either the fin is true, or the swordfish is true. In either case, the cells that would be affected by the swordfish reductions in the same box as the fin cannot be a 3. Any x-wing/seafood can be finned, and the fin allows sashimi variations where x-wing vertexes and entire swordfish/jellyfish rows can be missing. Check this thread for more info.
Back to top
View user's profile Send private message
keith
Hooked
Hooked


Joined: 07 Feb 2006
Posts: 35
Location: near Detroit, Michigan, USA

PostPosted: Thu Apr 13, 2006 9:56 pm    Post subject: Nishio is fishing? Reply with quote

David,

You may want to check this out:

http://users.pandora.be/vandenberghe.jef/sudoku/index.html?how2solve

(Carcul pointed me here.)

Here is a quote from the site:

Quote:

8. Nishio
Will entering a particular value prevent completion of the other placements of that value? If the answer if yes, then that candidate can be eliminated.
Given a value and a candidate cell, the Nishio rule considers whether the placement of the given value within the given cell would allow the remaining instances of that value to be placed. The remaining placements have to be trivial, i.e. each value has to be placed in a row, column or box where there exists just a single candidate cell - where no trivial placement exists, the candidate can not be eliminated. When the remaining values cannot be placed, the initial candidate can be eliminated.

It's rather difficult to understand what is happening here. But when we look back to the proof of the X-Wing, it becomes clear. The Nishio pattern works just that way. We apply a candidate for a value as part of the solution and look if there are conflicts with other candidates. This is done with recursive elimination, each time a candidate is solved all other possible candidates of the same units are eliminated and new single candidates come up, which give new eliminations and so on. The Nishio pattern stops, when there is a unit with no candidates left for the value, which means, it was a bad guess, and the original candidate can never be part of the solution and can be eliminated. Or when no more single candidates for the value can be found, which means that the original candidate can't be eliminated (yet). Remark that not all patterns are detected with Nishio, some patterns give also an impossible situation, but never end up to a unit with no possible candidates left. See, the Generalized X-Wing for an example. These patterns can be found when not only single candidates are eliminated, but also single unit candidates, X-Wings, and so on.

It is clear now, the Nishio pattern is a generalization of the X-Wing, Swordfish.

Some people say, that the Nishio pattern isn't a real pattern, but a trial-and-error method. But what is trail-and-error? When we look for a single candidate and we take a cell and try if 1 goes in, 2 goes in, 3 goes in ... until we have test all the values, or until we found 2 possible candidates for the cell. This is also a trial-and-error method, isn't?



I really don't fully understand this yet, but it seems you may have figured out that templates are the dual of nishio and that they are (both) generalized fishes. I am impressed!.

Best wishes,
Keith
Back to top
View user's profile Send private message
David Bryant
Gold Member
Gold Member


Joined: 20 Jan 2006
Posts: 86
Location: Denver, Colorado

PostPosted: Fri Apr 14, 2006 4:18 pm    Post subject: Why is it seafood? Reply with quote

myth jellies wrote:
Any x-wing/seafood can be finned, and the fin allows sashimi variations where x-wing vertexes and entire swordfish/jellyfish rows can be missing. ...

Yes, I've read some of those discussions already. Thanks for the link.

Here's a question for you -- who turned the "swordfish" into "seafood"?

As far as I can tell, the first person to speak of a "swordfish" was rubylips. Here's a quote from the "techniques" page on that site.
rubylips web site wrote:
The long sequences of two-candidate rows, columns and boxes are called 'strings' in the Solver source code. I see two wings - an upper wing and a lower wing - separated by struts, which resembles an old biplane. The presence of strings reminded me of the expression 'Flying Stringbag' - the nickname for the venerable Fairey Swordfish - hence the name given to this strategy type.

So it appears that the "swordfish" was named after an airplane, not a marine vertebrate. I'm wondering who started the trend towards "jellyfish," "sashimi," and all the rest of it? dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Ruud
Site Owner
Site Owner


Joined: 30 Dec 2005
Posts: 601

PostPosted: Fri Apr 14, 2006 5:44 pm    Post subject: Reply with quote

Hi David,

You are talking to 2 of the culprits.

I'm not sure who came up with 'Jellyfish', but when I needed a name for the general technique, I coined 'seafood', which ended up in Gaby Vanhegan's sudoku dictionary and then got quick acceptance by the community. I was not aware of the airplane connection. Interesting! However, the 'turbot fish' was also introduced around the same time by Nick67.

Myth Jellies (linked to jellyfish?) came up with the filet-o-fish naming, with the fins and sashimi varieties. I know that MJ hinted at a long story behind the naming in his initial post on the sudoku player's forum, but maybe he can tell us more about it here.

You're writing a sudoku history? Wink

cheers,

Ruud.
Back to top
View user's profile Send private message Send e-mail
David Bryant
Gold Member
Gold Member


Joined: 20 Jan 2006
Posts: 86
Location: Denver, Colorado

PostPosted: Sat Apr 15, 2006 6:47 pm    Post subject: I'm just curious Reply with quote

Ruud wrote:
You're writing a sudoku history?

No, I'm not trying to write a history of sudoku. I'm just curious about words, and how old ones come to be associated with new concepts.

I first learned about the "swordfish" sometime last summer ... late July or early August, I think. Anyway, the rubylips site was one of a very few online solvers available then, so I read through the techniques section and tried out some of the sample puzzles. I even went and read some of the programmers forum stuff, and from all that reading I gathered that "rubylips" was the person who had stuck the name "swordfish" on a 3x3 cyclical pattern.

If I had been naming it, I would have called it "tic-tac-toe." I don't have the vivid imagination some of the rest of you are blessed with! dcb
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Myth Jellies
Hooked
Hooked


Joined: 04 Apr 2006
Posts: 42

PostPosted: Sun Apr 16, 2006 8:50 am    Post subject: Re: Why is it seafood? Reply with quote

David Bryant wrote:
Here's a question for you -- who turned the "swordfish" into "seafood"?

As far as I can tell, the first person to speak of a "swordfish" was rubylips. Here's a quote from the "techniques" page on that site.
rubylips web site wrote:
The long sequences of two-candidate rows, columns and boxes are called 'strings' in the Solver source code. I see two wings - an upper wing and a lower wing - separated by struts, which resembles an old biplane. The presence of strings reminded me of the expression 'Flying Stringbag' - the nickname for the venerable Fairey Swordfish - hence the name given to this strategy type.

So it appears that the "swordfish" was named after an airplane, not a marine vertebrate. I'm wondering who started the trend towards "jellyfish," "sashimi," and all the rest of it? dcb


I came on the scene after swordfish, jellyfish, turbot fish and seafood (along with a generic NxN swordfish term) were all coined; so I had nothing to do with them. I was unaware that the swordfish referenced a biplane rather than the fish.

So when I came up with an idea that allowed for only a piece of the generic NxN swordfish reduction to be valid, it seemed appropriate to call it a fillet. When another related observation allowed even more of the fish to disappear, I thought to honor the Japanese contributions to making the puzzle what it is today, and gave it the term sashimi. Someone else (vidarino) named the extra bits mucking up the swordfish pattern the fin, and the term finned x-wing, etc. seems to have superceded both fillets and sashimi. It just goes to show you that the public will always have the final say in what name sticks to a new method Laughing
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    SudoCue Users Forum Index -> Solving Techniques & Tips All times are GMT
Page 1 of 1

 
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


Powered by phpBB © 2001, 2005 phpBB Group