New Solving Technique (I think)

Everything about Sudoku that doesn't fit in one of the other sections

Re: New Solving Technique (I think)

Postby ronk » Fri Jan 27, 2012 1:11 am

daj95376 wrote:
ronk wrote:For the Tungsten Rod above, I would like to know the eliminations for <134567>-templates.

Code: Select all
 <134567>-templates      r2c5<>39; r3c5<>36; r4c4<>35; r1c5<>3; r3c2<>4;
                         r15c1,r1c4,r4569c5,r128c6,r56c9<>5; r78c4<>6;
                         r3c36,r7c7<>7
   elims = 25
   combinations = 282

That was quick, thanks. And wow, the only way I can get that many eliminations with base sets\cover sets is to add four URs. But even then, the eliminations are not identical. Templates has some eliminations that base\cover doesn't ... and vice versa.

Does templating somehow have uniqueness embedded? Can someone devise a simple test to determine this?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: New Solving Technique (I think)

Postby denis_berthier » Fri Jan 27, 2012 7:22 am

pjb wrote:Briefly, one takes the first pattern of number 1 and adds the 9 addresses to an array. One then takes the first pattern of number 2 and checks if any one of its 9 addresses coincides with one of those of the pattern for 1. If not, its 9 addresses are added to the array, otherwise it is discarded and the second pattern of number 2 is taken. By working through digits 1 to 9 using this process, one eventually ends up with all 81 addresses in the array, and the puzzle is solved.


I've just found this thread.
I'd formalise and summarise your method as follows, which makes it appear as standard depth-first search (DFS) applied to templates.
If I'm right, then what's new (AFAIK, but I don't know POM) is the idea of applying DFS to templates instead of candidates.

Definition: a template is a set of 9 cells such that no two of them see each other.
It is easy to see that there are 46,656 templates (as already mentioned by daj95376), independent of any particular puzzle; they can be pre-computed and ordered before any resolution starts.

Definition: two templates are compatible if they are disjoint (as sets of cells).
As the test for set disjointness can be very fast, it doesn't seem useful to pre-compute this compatibility relation.

Definition: a template for a digit k is a template all the cells of which are assigned value k.

Definition: given a puzzle P, a template T for a digit k is compatible with the clues of P if:
- all the clues for digit k in P are in cells of T,
- all the clues for other digits in P are in cells not in T.

Definition: Sudoku problem: find 9 templates, one for each digit, such that:
- each of them is compatible with the clues,
- they are pairwise compatible.

Basic resolution procedure: depth-first-search (DFS), with maximum depth 9
for i=1 to 9
- choose the next template Ti (in the fixed vector of templates) for number i, compatible with the clues and with the previously chosen Tj's
- if no such template can be found, backtrack to the previous value of i
[add some exit condition]

Output (as usual for DFS):
Depending on the exit condition: either 0, 1, n, or all the solutions

Range of application:
any puzzle, with 0, 1 or more solutions

Optimisations:
- use this procedure only after all the eliminations and assertions that can be obtained from some predefined set of rules (for this, define the notion of compatible with a PM, in the obvious way, extending "compatible with a puzzle");
- choose more smartly the order of the digits (e.g. choose at each step the digit that has the fewest templates compatible with the current situation);
Not sure that any of this wouldn't degrade speed instead of improving it.


Questions (maybe close to already raised ones, but maybe different):
1) What is the smallest value of k such that, for all the minimal puzzles P, using only this basic procedure (excluding any rule application), but after a proper re-ordering of the digits, the full solution of P can be obtained, after templates have been chosen for only k or fewer digits, by a sequence of single-possibility choices (of templates for the remaining digits)?
Alternative formulation: applying BFS (breadth-first search) instead of DFS to templates, what is the maximal depth of search necessary to solve all the minimal puzzles?

2) What is the current largest known value of the minimum k for a minimal puzzle?

3) Is there any correlation between the difficulty of a minimal puzzle (say its SER) and its minimum k?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: New Solving Technique (I think)

Postby champagne » Fri Jan 27, 2012 10:18 am

Tungsten Rod in the way it is shown here (does not seem to be the original one) has an EXOCET pattern 157.

As a matter of fact, combining floors 157, we get about 20 eliminations.

Any group of floors of higher degree having these 3 floors will have at least these eliminations

champagne

EDIT change 136 to 157 to correct an error explained in a separate post
Last edited by champagne on Sat Jan 28, 2012 2:01 am, edited 1 time in total.
champagne
2017 Supporter
 
Posts: 5675
Joined: 02 August 2007
Location: France Brittany

Re: New Solving Technique (I think)

Postby ronk » Fri Jan 27, 2012 12:37 pm

champagne wrote:Tungsten Rod in the way it is shown here (does not seem to be the original one) has an EXOCET pattern 136. As a matter of fact, combining floors 136, we get about 20 eliminations.

The Tungsten (Tungston) Rod above matches coloin's post of Aug 31, 2008. If you have an earlier publication which is different, please be so kind as to post a link.

BTW I believe the appropriate term in this thread is template, not floor.

denis_berthier wrote:Definition: a template is a set of 9 cells such that no two of them see each other.
It is easy to see that there are 46,656 templates (as already mentioned by daj95376), independent of any particular puzzle; they can be pre-computed and ordered before any resolution starts.

Definition: two templates are compatible if they are disjoint (as sets of cells).
As the test for set disjointness can be very fast, it doesn't seem useful to pre-compute this compatibility relation.

Definition: a template for a digit k is a template all the cells of which are assigned value k.

Thanks for the definitions, but would you please revise them to be compatible with dukuso's definitions which I replicated earlier in this thread?

I've never quite understood the need for the difference between ...
Code: Select all
 . . O | . . . | . . .                . . 1 | . . . | . . .
 . . . | . . . | . . O                . . . | . . . | . . 1
 . . . | . . O | . . .                . . . | . . 1 | . . .
-------+-------+-------              -------+-------+-------
 . . . | O . . | . . .                . . . | 1 . . | . . .
 O . . | . . . | . . .      and       1 . . | . . . | . . .
 . . . | . . . | . O .                . . . | . . . | . 1 .
-------+-------+-------              -------+-------+-------
 . . . | . O . | . . .                . . . | . 1 . | . . .
 . O . | . . . | . . .                . 1 . | . . . | . . .
 . . . | . . . | O . .                . . . | . . . | 1 . .

       1-rookery                           1-template

... or ...
Code: Select all
                                                   
 . . O | O . . | . . .                . . 1 | 2 . . | . . .
 O . . | . . . | . . O                2 . . | . . . | . . 1
 . . . | . . O | . . O                . . . | . . 1 | . . 2
-------+-------+-------              -------+-------+-------
 . . O | O . . | . . .                . . 2 | 1 . . | . . .
 O . . | . O . | . . .      and       1 . . | . 2 . | . . .
 . . . | . . . | O O .                . . . | . . . | 2 1 .
-------+-------+-------              -------+-------+-------
 . . . | . O O | . . .                . . . | . 1 2 | . . .
 . O . | . . . | . O .                . 1 . | . . . | . 2 .
 . O . | . . . | O . .                . 2 . | . . . | 1 . .

       2-rookery                           2-template

... but let's stick with the great dukuso's lead.

[edit: added 2-rookery and 2-template illustrations]
Last edited by ronk on Fri Jan 27, 2012 2:37 pm, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: New Solving Technique (I think)

Postby denis_berthier » Fri Jan 27, 2012 2:15 pm

ronk wrote:Thanks for the definitions, but would you please revise them to be compatible with dukuso's definitions which I replicated earlier in this thread?

A definition is good if it is simple and it leads to results or to a clearer view, not because it was written by "great dukuso" or any of your gurus.
You've probably missed the main point of my post: pjb's algorithm is DFS.

I think the notion of a k-rookery can only make pjb's algorithm look more complex than it is and my definitions are the simplest ones for describing it. It's a pity pjb has disappeared from this thread.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: New Solving Technique (I think)

Postby champagne » Fri Jan 27, 2012 3:06 pm

ronk wrote:The Tungsten (Tungston) Rod above matches coloin's post of Aug 31, 2008. If you have an earlier publication which is different, please be so kind as to post a link.

BTW I believe the appropriate term in this thread is template, not floor.




in the post, we find 2 morphs of "tugston rod".

I have in my data base the second one, choosen by tarek for its data base of hardest. The source for tugston rod in my database is tarek's file


in a PM, we have usually and at most 9 floors (active). I believe the above statement that there are 46,656 templates. It would be very surprising that both terms have the same definition.

A floor is the fraction of a PM containing all the candidates of the same digit. If I got it, we still have several templates valid for a floor unless all occurences of that digit are assigned.

champagne
champagne
2017 Supporter
 
Posts: 5675
Joined: 02 August 2007
Location: France Brittany

Re: New Solving Technique (I think)

Postby ronk » Fri Jan 27, 2012 3:17 pm

denis_berthier wrote:
ronk wrote:Thanks for the definitions, but would you please revise them to be compatible with dukuso's definitions which I replicated earlier in this thread?

A definition is good if it is simple and it leads to results or to a clearer view, not because it was written by "great dukuso" or any of your gurus.
You've probably missed the main point of my post: pjb's algorithm is DFS.

You're being presumptuous IMO. You don't know whether my use of "great" was complimentary, sarcastic or merely a copy of coloin's expression earlier ... and "no", I didn't miss your main point. Moreover, as you've a history of stomping on the terminology of others, I didn't actually expect you to accept my suggestion, but it needed to be made.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: New Solving Technique (I think)

Postby denis_berthier » Fri Jan 27, 2012 4:07 pm

champagne wrote:A floor is the fraction of a PM containing all the candidates of the same digit.

Taking this as the definition of a floor and my above definition of a template for the purposes of the current discussion, I agree with your next statement:
champagne wrote:If I got it, we still have several templates valid for a floor unless all occurences of that digit are assigned.


pjb's algorithm implements standard DFS (depth in DFS corresponding to the number of floors under consideration), progressively reducing the number of possibilities for the remaining floors.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: New Solving Technique (I think)

Postby ronk » Fri Jan 27, 2012 4:29 pm

denis_berthier wrote:
champagne wrote:A floor is the fraction of a PM containing all the candidates of the same digit.

Taking this as the definition of a floor and my above definition of a template for the purposes of the current discussion, I agree with your next statement:
champagne wrote:If I got it, we still have several templates valid for a floor unless all occurences of that digit are assigned.

Although I dislike redefinition of the floor term, I appreciate the distinction between a "floor" and a 1-template. However, I have two observations:
  • The "floor" must include clues and placements as well as candidates of the same digit to accomplish template selection, and
  • Your definiton for "template" is non-specific as to a digit, so your statement above would need to be "a template for a digit", rather than merely "a template."
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: New Solving Technique (I think)

Postby denis_berthier » Fri Jan 27, 2012 4:42 pm

ronk wrote:
denis_berthier wrote:
champagne wrote:A floor is the fraction of a PM containing all the candidates of the same digit.

Taking this as the definition of a floor and my above definition of a template for the purposes of the current discussion, I agree with your next statement:
champagne wrote:If I got it, we still have several templates valid for a floor unless all occurences of that digit are assigned.

Although I dislike redefinition of the floor term, I appreciate the distinction between a "floor" and a 1-template. However, I have two observations:
  • The "floor" must include clues and placements as well as candidates of the same digit to accomplish template selection, and
  • Your definiton for "template" is non-specific as to a digit, so your statement above would need to be "a template for a digit", rather than merely "a template."

I concur on both points.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: New Solving Technique (I think)

Postby ronk » Fri Jan 27, 2012 4:53 pm

champagne wrote:
ronk wrote:The Tungsten (Tungston) Rod above matches coloin's post of Aug 31, 2008. If you have an earlier publication which is different, please be so kind as to post a link.

in the post, we find 2 morphs of "tugston rod". I have in my data base the second one, choosen by tarek for its data base of hardest. The source for tugston rod in my database is tarek's file

At the link I provided, the 2nd is a canonicalization of the puzzle, which coloin posted and stated "as a reference", which most people would not take as the puzzle.

As to tarek's "database of hardest", you again provide no link. However, if you are referring to his posts here and/or here, both match the unmorphed Tungston Rod puzzle used earlier in this thread by both dobrichev and daj95376.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: New Solving Technique (I think)

Postby daj95376 » Fri Jan 27, 2012 4:55 pm

I hate technical discussions on Sudoku because everyone has their own (favorite) definitions/terminology. Technically speaking ...

a k-rookery is a subset of the 81 cells in a 9*9 square which contains exactly k-cells
from each row,column,block

a k-template is a k-rookery whose 9*k cells are filled with numbers from {1,2,..,k},
such that the rookery-cells from each row,column,block contain each digit from {1,..,k}
exactly once

If we follow dukuso's definition to the letter, then ...

Code: Select all
 <134567>-templates      r2c5<>39; r3c5<>36; r4c4<>35; r1c5<>3; r3c2<>4;
                         r15c1,r1c4,r4569c5,r128c6,r56c9<>5; r78c4<>6;
                         r3c36,r7c7<>7
   elims = 25
   combinations = 282

... is not a 6-template because it is not filled with values = {1,2,3,4,5,6}.

As for me, a 1-rookery is equivalent to my understanding of "template" as used by Ruud in the Programmers' forum. (Now, of course, I'll be forced to reread that thread. :x )

This (again) leaves us without a name for this class of template grouping. I suggest: 6-daj95376. :lol:
Last edited by daj95376 on Fri Jan 27, 2012 6:33 pm, edited 4 times in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: New Solving Technique (I think)

Postby denis_berthier » Fri Jan 27, 2012 5:11 pm

Hi daj95376,
nice example of an abstruse definition that bites its own tail

But I think there are two problems that should be put on an equal footing in discussions such as in this thread:
- the vocabulary pb you mention, including the generally vague "definitions" of terms
- the quick divergence from the initial topic

Here, k-templates and k-rookeries, whatever definition you give for them, are merely irrelevant to pjb's algorithm.

Moreover, the two problems are intimately related, as this irrelevance can only be seen when the good definitions become available.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: New Solving Technique (I think)

Postby champagne » Fri Jan 27, 2012 5:26 pm

ronk wrote:At the link I provided, the 2nd is a canonicalization of the puzzle, which coloin posted and stated "as a reference", which most people would not take as the puzzle.

As to tarek's "database of hardest", you again provide no link....



I am not sure this is worth more comments

tarek is clearly not part of "most people"

champagne
champagne
2017 Supporter
 
Posts: 5675
Joined: 02 August 2007
Location: France Brittany

Re: New Solving Technique (I think)

Postby ronk » Fri Jan 27, 2012 5:39 pm

champagne wrote:
ronk wrote:At the link I provided, the 2nd is a canonicalization of the puzzle, which coloin posted and stated "as a reference", which most people would not take as the puzzle.

As to tarek's "database of hardest", you again provide no link....

I am not sure this is worth more comments
tarek is clearly not part of "most people"

Then I shall summarize. tarek, dobrichev, daj95376 and I are all using the original Tungston Rod posted by coloin. You apparently are using a different morph.

But you're right about this not being worth more comment.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to General