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 daj95376 » Fri Jan 27, 2012 5:58 pm

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.

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.

How my solver sees it:

A template is a set of 9 cells such that no two of them see each other.
There are 46,656 distinct templates that are independent of any particular value. They are pre-computed, ordered, and loaded from a file before the first puzzle is starts.

A template is assigned to digit k when all of its cells conform to: clue/solved for k, or contains k as a candidate in the current PM/grid. No template is assigned to more than one choice for k; but templates will exist that can't be assigned to any choice for k.

Note: During "template reduction", templates can be unassigned to digit k when conflicts are detected between them and non-k templates.
Last edited by daj95376 on Fri Jan 27, 2012 6:10 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: New Solving Technique (I think)

Postby champagne » Fri Jan 27, 2012 6:02 pm

ronk wrote:
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.



how is it possible to be so false!!!

I don't care about the "best value"

My source is a data base published by tarek.

That's it.

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

Re: New Solving Technique (I think)

Postby denis_berthier » Fri Jan 27, 2012 6:27 pm

daj95376 wrote:A template is assigned to digit k when all of its cells conform to: clue/solved for k, or contains k as a candidate in the current PM/grid.

This corresponds to the notion of a template for a digit k being compatible with a PM (an extension of my definition of "compatible with a puzzle", that I mentioned quickly in my first post).
Such an extension is needed in case one wants to mix pjb's technique with resolution rules based on candidates.
Interestingly, it is not needed in case one uses only pjb's technique. This technique in its pure form can be formulated without the notion of a candidate.

I don't have a solver based on templates and I currently don't have much time for Sudoku. Does your solver implement pjb's technique as I described it? If so, did you already explore questions similar to those , at the end of my first post, about the smallest k (the smallest number of floors in Champagne's vocabulary) before a solution can be obtained with unique choices? (if you're a programmer, I think the BFS form of the question is simpler in its formulation).
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: New Solving Technique (I think)

Postby ronk » Fri Jan 27, 2012 6:44 pm

champagne wrote:My source is a data base published by tarek.

Other than the <136> ALS marker, you've posted nothing concrete about the Tungston Rod puzzle you're using. What is your link to tarek's database? What is the 81-character puzzle you are reading from that database?
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: New Solving Technique (I think)

Postby ronk » Fri Jan 27, 2012 9:34 pm

daj95376 wrote: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 )

Assume you/re referring to Ruud's Has anyone tried solving these puzzles using templates? thread of Sept 2005. Pretty much shoots a hole in the idea that pjb's strategy might be a new one.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: New Solving Technique (I think)

Postby daj95376 » Fri Jan 27, 2012 10:27 pm

denis_berthier wrote:
daj95376 wrote:A template is assigned to digit k when all of its cells conform to: clue/solved for k, or contains k as a candidate in the current PM/grid.

This corresponds to the notion of a template for a digit k being compatible with a PM (an extension of my definition of "compatible with a puzzle", that I mentioned quickly in my first post).
Such an extension is needed in case one wants to mix pjb's technique with resolution rules based on candidates.
Interestingly, it is not needed in case one uses only pjb's technique. This technique in its pure form can be formulated without the notion of a candidate.

I don't have a solver based on templates and I currently don't have much time for Sudoku. Does your solver implement pjb's technique as I described it? If so, did you already explore questions similar to those , at the end of my first post, about the smallest k (the smallest number of floors in Champagne's vocabulary) before a solution can be obtained with unique choices? (if you're a programmer, I think the BFS form of the question is simpler in its formulation).

In your first paragraph, it appears that we are in agreement, but from slightly different perspectives. I don't see the need to split hairs over the differences in our perspectives.

As for your second paragraph, the answer is essentially NO. My solver does not implement pjb's technique. My template() routine is used primarily as support to my fish() routine. It does have the ability to perform what I call "template reduction", but it's rudimentary in its scope and seldom needed.

As to pjb's initial request, I only recall suggestions on how to improve its efficiency -- not its actual use by anyone. There were, however, tangent discussions that followed. Most involving the use of templates from a reduced set of values to determine eliminations. Once I understood how these eliminations were derived, I made a copy of my template() routine and modified it to try and answer some of the questions that arose in this thread. As of now, I can find eliminations for 4/5/6/7-template scenarios. I do not plan to keep this copy of template() active in my solver.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: New Solving Technique (I think)

Postby champagne » Sat Jan 28, 2012 2:20 am

champagne wrote: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


I have to apologize about the original post.

When I checked the Tugson rod puzle in my data base, I saw the EXOCET, but I noticed it was a different pattern.

Picking up the current pattern in that thread, I made a mistake and picked in fact "fata morgana".
Unhappily, "fata morgana" has the same kind of EXOCET pattern and I took it to write the post.

To give of more detailed answer,t he PM at the moment the solver looks for the EXOCT is the following, nearly at the start
Code: Select all
||34589 4568  34689  |12356 123569 15689 |24    1389  7   
||3589  2     3789   |4     13579  15789 |1389  6     389 
||1     4678  346789 |2367  23679  6789  |5     389   24   
--------------------------------------------------------
||358   9     1378   |13567 13567  2     |1378  4     358 
||2345  1457  12347  |8     13457  157   |6     13579 2359
||6     14578 123478 |9     13457  157   |12378 13578 2358
--------------------------------------------------------
||2489  1468  5      |1267  12679  3     |4789  789   4689
||49    3     1469   |1567  8      15679 |479   2     4569
||7     68    2689   |256   2569   4     |389   3589  1   


The potential eliminations with floors 157 are the following

5: r1c146 r2c6 r4c45 r5c159 r6c59 r8c6 r9c5
7: r3c36 r7c7
39r2c5
6r8c4

The solver finds 29 permutations so I guess that a template analysis should find the same


The EXOCET pattern has a base r56c6 and a target r2c5 r8c4

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

Re: New Solving Technique (I think)

Postby pjb » Sat Jan 28, 2012 5:10 am

daj95376 wrote:

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


Code: Select all
: 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


Hi daj95376

I guess I must be missing something, but could you possibly go into a bit more detail as to how you utilise the <134567>-templates to achieve these eliminations?
Thanks, pjb
pjb
2014 Supporter
 
Posts: 1693
Joined: 11 September 2011
Location: Sydney, Australia

Re: New Solving Technique (I think)

Postby denis_berthier » Sat Jan 28, 2012 6:44 am

ronk wrote:referring to Ruud's Has anyone tried solving these puzzles using templates? thread of Sept 2005. Pretty much shoots a hole in the idea that pjb's strategy might be a new one.


Good reference. I agree with your conclusion.

My own summary of Ruud's thread (disregarding the usual sterile considerations about whether it is logic or not) would include the following points:

- the algorithm was generally considered as brute force - which is also my opinion; notice that in Ruud's presentation, it doesn't have to be what I'd call template-DFS as in pjb's description, but the search graph is the same anyway; in any case it is a form of systematic search of this graph of combined-templates-for-digits;

- implementation details and efficiency matters were already considered there;

- the possibility of combining the algorithm with more classical techniques was also already considered there; notice that these are forms of pruning the search graph and they can in no way change its fundamental brute force nature, even though they can (partly) hide it;

- notice Ocean's smart remark about how to generate all the templates from a unique one, using the natural symmetry group (in group theoretic terms, the set of templates has a unique orbit under the symmetry group);

- pjb's remark here that it is a very efficient algorithm was already made at that time; but Ruud concluded that "DLX is definitely faster" although "templates have more flexibility";

- the last post in that thread is from Nov. 2006; I wonder if this technique has been used in the 5 1/2 years since then.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: New Solving Technique (I think)

Postby daj95376 » Sat Jan 28, 2012 7:59 pm

pjb wrote:I must be missing something, but could you possibly go into a bit more detail as to how you utilise the <134567>-templates to achieve these eliminations?

When you started this thread, I hadn't tried to manipulate templates using more than two values. After studying coloin's and ronk's comments, I was able to use more than two values.

I think the best way to describe my logic is to convert my C routine into something more readable. To that end, I will use indexing from 1..n on my routine that computes the results for a single 5-template.

My basic data structure is a bitmap. It stores a bit array of True(1)/False(0) states for the cells in a Sudoku grid.

Hidden Text: Show
Code: Select all
typedef     uint32  bitmap[3];   // unsigned three-word array totalling 96 bits


    bitmap  bmCands [9];   // for each value --  clues_solved_candidates in grid

    bitmap  NOTgrid [9];   // for each value --  eliminations

    bitmap  ORgrid  [9];   // for each value --  ORing of utilized templates

    bitmap  TPlist  [~];   // list of active templates for all values

    int     TPbase  [9];   // for each value -- index of first template in list

    int     TPcount [9];   // for each value -- number of templates in list


bmAND           operator to perform logical-AND operation on two bitmaps
bmOR            operator to perform logical-OR  operation on two bitmaps

bmINT           test for intersection between two bitmaps

bmCOMP()        complement the T/F states of a bitmap
ZERO()          a macro that uses memset() to zero an array

count_cells()   count the number of True states in a bitmap
multi_print()   prints eliminations stored in NOTgrid


/* -------------------------------------------------------------------------- */

static  void    n5_reduction( int v1, int v2, int v3, int v4, int v5 )
{
    int     i1, i2, i3, i4, i5, value;          // indexes
    int     combinations = 0, elims = 0;        // counters

    bitmap  bm_1, bm_2, bm_3, bm_4, bm_5;       // active bitmap for v1..v5

    bitmap  bm_12, bm_123, bm_1234, bm_12345;   // ORing of above bitmaps

    bitmap  bm_locked;   // cummulative ANDing of bm_12345 results


    ZERO  ( NOTgrid   );   // set all cells to False
    ZERO  ( ORgrid    );   // set all cells to False
    ZERO  ( bm_locked );   // set all cells to False
    bmCOMP( bm_locked );   // set all cells to True


    for i1 = 1..TPcount[v1]
    {
        bm_1 = TPlist[ TPbase[v1] + i1 ];   // template for v1

        for i2 = 1..TPcount[v2]
        {
            bm_2 = TPlist[ TPbase[v2] + i2 ];   // template for v2

            if ( bm_1 bmINT bm_2 )   continue;   // unacceptable

            bm_12 = bm_1 bmOR bm_2;

            for i3 = 1..TPcount[v3]
            {
                bm_3 = TPlist[ TPbase[v3] + i3 ];   // template for v3

                if ( bm_12 bmINT bm_3 )   continue;   // unacceptable

                bm_123 = bm_12 bmOR bm_3;

                for i4 = 1..TPcount[v4]
                {
                    bm_4 = TPlist[ TPbase[v4] + i4 ];   // template for v4

                    if ( bm_123 bmINT bm_4 )   continue;   // unacceptable

                    bm_1234 = bm_123 bmOR bm_4;

                    for i5 = 1..TPcount[v5]
                    {
                        bm_5 = TPlist[ TPbase[v5] + i5 ];   // template for v5

                        if ( bm_1234 bmINT bm_5 )   continue;   // unacceptable

                        combinations = combinations + 1;

                        bm_12345     = bm_1234 bmOR bm_5;

                        bm_locked    = bm_locked bmAND bm_12345;

                        ORgrid[v1]   = ORgrid[v1] bmOR bm_1;
                        ORgrid[v2]   = ORgrid[v2] bmOR bm_2;
                        ORgrid[v3]   = ORgrid[v3] bmOR bm_3;
                        ORgrid[v4]   = ORgrid[v4] bmOR bm_4;
                        ORgrid[v5]   = ORgrid[v5] bmOR bm_5;
    }   }   }   }   }


    for value = 1..9
    {
        if ( ( value == v1 ) or ( value == v2 ) or ( value == v3 )
                             or ( value == v4 ) or ( value == v5 ) )

            NOTgrid[value] = bmCands[value] bmNOT ORgrid[value];

        else

            NOTgrid[value] = bm_locked bmAND bmCands[value];

        elims = elims + count_cells( NOTgrid[value] );
    }


    if ( elims )
    {
        printf( "\n <%d%d%d%d%d>-templates   ", v1, v2, v3, v4, v5 );

        multi_print( NOTgrid );

        printf( "\n   elims = %d\n   combinations = %d\n", elims, combinations );
    }
}
_________________________________________________________________________________
Last edited by daj95376 on Sat Jan 28, 2012 8:15 pm, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Re: New Solving Technique (I think)

Postby JasonLion » Sat Jan 28, 2012 8:09 pm

I explored a breadth first multi-digit template solver, but it took too much memory to be useful. This topic is the first time I have run into a depth first multi-digit template solver.
User avatar
JasonLion
2017 Supporter
 
Posts: 621
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: New Solving Technique (I think)

Postby coloin » Sun Jan 29, 2012 2:25 am

Apologies to pjb for getting daj95376 to extend his re-introduction of templates as a solving technique.

I await whether the eliminations that are found for <134567> amount to what many feel as the opening in the Tungsten Rod puzzle.

Of course it should be said that dukuso never really took the credit he was due. here

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Template-depth of a puzzle

Postby denis_berthier » Sun Jan 29, 2012 7:20 am

JasonLion wrote:I explored a breadth first multi-digit template solver, but it took too much memory to be useful.

Errr, sorry if I induced you to try this. When I said that "the BFS form of the question is simpler in its formulation", I meant it with emphasis on the phrase "in its formulation". I didn't expect anyone would try to implement template-BFS directly.

Let me more precise about the questions I raised.
First, let it be clear that I'm speaking about the original template procedure, first introduced by Ruud and rediscovered by pjb, with the definition of a template as I formalised it above, consistent with those of Ruud and daj95376. I'm not speaking of the partial rookeries and partial templates also discussed in this thread (which now appear to be the notions through which the original concept has found a new life).

Background: all the known puzzles can be solved by T&E(2) - according to my definition of T&E (http://forum.enjoysudoku.com/post61854.html#p61854 and next posts), which I consider as the proper formalisation of the usual notion.
Corollary: all the known puzzles can be solved by BFS (pruned by Singles) at maximum depth 2.
Corollary of the corollary: all the known puzzles can be solved by template-BFS (pruned by Singles) at maximum depth 2. So if we accept pruning, my question has little interest (except if maximal depth could be reduced to 1 - which is unlikely).

But, consider the pure template-DFS algorithm based on templates without any reference to candidates and without any pruning (by elementary constraints propagation and/or Singles). I think this version of this algorithm can be extremely fast because it needs to compute only set intersections.

For a puzzle P, define TD(P), the template-depth of P, as the minimum number of digits such that:
there is a way of choosing templates for TD(P) digits and a way of ordering the remaining 9 - TD(P) digits such that there is at each step a unique possibility for the templates for each of these remaining digits;
said in vaguer terms, after templates have been properly chosen for TD(P) digits, the puzzle can be solved by "template-Singles".

TD(P) is an intrinsic property of P.
TD(P) can also be described in a conceptually (but not computationally) simpler way: TD(P) is the template-BFS depth of P (considering that single choices don't increase depth).


Additional background:
There is an easily provable relationship between the T&E-depth of a puzzle and its complexity in terms of braids:
- depth 0 = solvable by Singles
- depth 1 = solvable by braids
- depth 2 = solvable by B-braids
There is an additional experimental result: depth 2 = solvable by B7-braids, for all the known puzzles.

By analogy with the T&E case, my questions are:
- what is the maximal template-depth for all the minimal puzzles?
- is there any relationship between template-depth and difficulty (measured e.g. by SER)?

(Notice that the above analogy is purely formal, as T&E excludes any form of guessing, whereas template-DFS or template-BFS do not.
Maybe a better analogy for template-depth would be with backdoor size - the max value of which is 3 for all the known puzzles.
Unfortunately, there doesn't seem to be much correlation between backdoor size and difficulty.)
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: New Solving Technique (I think)

Postby dobrichev » Sun Jan 29, 2012 11:09 am

Hi,

I am doubting we are using the same language.

Assume the following hypothetical solver.
1) Take a puzzle having unique solution.
2) Initially assign all possible 46656 templates as candidates for solution.
3) Eliminate some of the templates "directly" contradicting the givens (perform "singles", no matter what exactly it includes). Loop until no further eliminations are possible.
4) Optional, applicable if we are searching for "pencilmark elimination". Save the output of step 3) in the form of union of all remaining templates for each of the digits. One set per digit, 9 sets in total representing the pencilmarks.
5) Reorder the digits in all possible 9! ways and perform 9 nested loops by combining all "compatible" templates for each combination of the digits. Each of the 9! loops will lead to the same solution but with different intermediate results.

Now, in addition to the solution, what are we searching for?

To my understanding, one of the goals discussed here and formalized by daj95376 here is to compute the pencilmarks (again as union of all templates) at each level of the nested loops and to compare them to those obtained at step 4). Any difference is an "elimination". Searching is for "depth" d = nesting level, and the "digits" = top d digits participating in the chosen one of 9! permutations. Reducing the task to this search makes all inner loops (from d + 1 to 9) unnecessary. Answer looks like "puzzle EM has minimal depth 4 and it is based on digits <1267>".
Only set operations are used.
What are the next steps? Obviously the "pencilmark" elimination leads to one or more "template eliminations". Loop until all but one of templates for digit remain?

Other approach, which is closer to my understanding of denis_berthier's goal is to enumerate all possible 9! solution paths searching for those which lead to earlier "elimination of all but one templates for a digit from now on".
For example, one of the possible 9! paths for EM is examining the permutation <123456789> which leads to the following iteration counts during the nested loops.
Template count after step 3) (with some additional eliminations which correctness depend of "template singles" definition).
33 35 130 32 18 33 8 148 18
Number of iterations of each of the 9 nested loops (code is here).
33 383 13741 55057 60733 32272 18 1 1
The rightmost counter is the number of solutions.
Are we searching for those of 9! permutations where the sequence of 1-s at the right starts earlier? If so, one of the candidates for the answer is "For EM puzzle there are 18 valid combinations of templates for digits <1234567>, one of them is solved later by template-singles and therefore the depth of the puzzle is 7". If any of the rest 9!-1 permutations lead to only two 1s at the end, then this puzzle has minimal depth of 7.
Only set operations are used.
Berthier, is this your understanding of "template singles"?

I attempted to discuss a possible relationship between template approach and other rating methods from different perspective here and found that it is too complex for our current knowledge.

Cheers,
MD
dobrichev
2016 Supporter
 
Posts: 1316
Joined: 24 May 2010

Re: Template-depth of a puzzle

Postby ronk » Sun Jan 29, 2012 11:33 am

denis_berthier wrote:I'm not speaking of the partial rookeries and partial templates also discussed in this thread (which now appear to be the notions through which the original concept has found a new life).

Assuming by "partial template" you mean a template for less than 9 rows, 9 columns and 9 boxes, I actually don't recall anyone doing that in this thread ... yet, but IMO if it's worth mentioning, then it's also worth a link or two (on your part for clarification).

That said, I certainly hope one outcome of this exercise is to identify new "partial templates", i.e., new patterns, that perform most, or even all, of the eliminations of the "full templates." Like Ruud wrote here, "I ... wonder if it could be used to detect new patterns and deductive rules."
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to General