The New Sudoku Players' Forum

[Allan Barker]

Champagne,

I think what you have found is FM loop 3 in the series of 3 loops. I list them below as 1, 2, 3a, and 3b. Each solutions is made by adding more linksets. However, this makes multiple overlaping solutions, so the rank is not really 11, it is probably still 1. Total number of sets for loop3 is 51 if all link sets are included.

Code: Select all

Eham 76 Nodes, Rank 11:
     20 Sets = {5n46 1b234678 3b124689 6b124689}
     31 Links = {1r159 3r2569 6r1458 1c1469 3c1467 6c3469 1n5 3n46
                 4n2 6n8 7n46 9n5}

1.  r4c2<>2, r4c2<>4
2.  r1c3<>6, r5c2<>6, r5c3<>6, r8c9<>6, r2c1<>3, r9c7<>3
3a. r5c8<>3, r6c1<>3, r9c4<>3, r9c6<>3,
3b. r1c4<>6, r1c6<>6, r4c9<>6, r5c7<>3,

Champagne wrote

Code: Select all

N4,2 N5,4 N5,6 N7,7 N8,9 N9,2 N9,5 N9,7
1B2 1B3 1B4 1B6 1B7 1B8
3B1 3B2 3B4 3B6 3B8 3B9
6B1 6B2 6B4 6B6 6B8 6B9

I found this by hand based on your 18 box sets/ 6 per rookery. The only difference is:
1. You have no R,C linksets.
2. You have 8 N (cell) sets (versus my 10) first 4 are the same.

I tried your linksets but got no eliminations.
Could it be that 'slimfast' has not learned the proper way to diet?

2D grid image. Click for enlarged view.



Loop 3 clears the first three regions in the below path. I wonder what happened to p259?

Code: Select all

Gray bars = no. of permutations at each set addition.
Blue line: no. of total eliminations.
Red line: no. of total assignments.
Below: eliminated note, marked at correct horiz. position.

[champagne]

I think what you have found is FM loop 3 in the series of 3 loops.

No surprise, I am confident that the global view is correct, so loop3 must exist. I'll study it later.

I think that in a solver you should first apply the simplest loop, and then restart the search on the reduced map of candidates. This is a very general strategy.

At most, you could apply in once actions of "nearly equivalent" complexity.

So loop3 would have a different shape in that strategy.

Could it be that 'slimfast' has not learned the proper way to diet?

I got to the same conclusion You know, diet is a very hard program.

The problem is that where we are after the "global view" i we have two main ways to go ahead:

1) restarting from the 112 sets a building program, but then I would benefit of your experience in the way you add sets to come to the adequate configurations,


2)sticking as a preliminary step to a "slimfast" program including appropriate constrainsts to have a good chance to reach the relevant sub groups.

I am thinking of following constraints:

- Open a list of sets to keep anyway and put in it all sets attached to sets bearings actions (eliminations or assignments)

- Force the sets to be a block (no detached set or group of sets).

BTW, I noticed that with detached sets, looking for permutations can be highly time consuming.

The minimum use of your process I have in mind is to look for unusual "fishy patterns" before I start tagging. I forecast in that case an acceptable processing time.

Even in that case, I have to achieve a good handling of the group of sets (27) to come to the MSG.

For wider cases, I am thinking more of using it in a search of quick solutions, keeping my tagging as basic case (much faster up to now ).

Loop 3 clears the first three regions in the below path. I wonder what happened to p259?

No idea for the time being

champagne

[Allan Barker]

Champagne,

Since I am a bit behind finishing my basic description of solving with permutations, I will put a preliminary copy here. The only difference is this is brief and not carefully checked. Later I will replace this with a referecne to the finishedwork.

The only thing you might want is about selecting the next set, which is most inportant in keeping the number of permutations down. Aslo see about starting different kinds of logic.

PART I, Second Order Solver - Permutations

Basic Sets

Basic sets are the 324 given constraints in Sudoku expressed as sets. There are 4 groups of 81 sets each for rows, columns, cells, and boxes. Each conventional row has 9 row sets, one for each digit.

Permutations

A permutation is one possible (legal) arrangement of candidates for any form of logic including sets, chains, fish, or an entire puzzle. An unsolved puzzle can have an extreme number of permutations. A valid solved puzzle has only one permutation, which is the answer. Each solution to a non-unique puzzle is a different permutation.

Code: Select all

A set with 3 candidates, A, B, C, has 3 legal permutations.

set{A, B, C}  =  100, 010, 001

The permutations of a basic set are called candidate vectors. The candidate vectors for any basic set are orthogonal, i.e., they cannot be combined.

Permutation Database

A permutation database D is simple, it a list of permutations for some logic L where each column represents a candidate. It is useful to have a mask to know which candidates are already in D. The database for the single set above is:

Code: Select all

cand. ABC--
mask  11100
p1    100..
p2    010..
p3    001..

Adding Permutations

Finding all legal permutations for any logic is done by adding the permutations of all subunits that make up the logic. Subunits are usually basic sets but can be chains, ALS, etc. The single operation of permutation addition does all the logic work of the solver:

Adding two permutations P1 and P2 requires that all shared candidates must have the same value. The resulting permutation then contains all candidates from P1 and P2.

Code: Select all

X-Wing Example

(1) = true candidate, (0) = false candidate, (.) = empty location

Row{A,B}   = (1,0),(0,1)
Row{C,D}   = (1,0),(0,1)
Col{A,C,X} = (1,0,0),(0,1,0),(0,0,1)
Col{B,D}   = (1,0),(0,1)

1. Add first row to the database
 
ABCDE  (database)
10... 
01... 

2. Adding remaining sets to the database

 ABCDE    +(..CD.)  +(A.C.X)  +(.B.D.)
 10...  --> 1010. -->
            1001. --> 10010 --> 10010 
 01...  --> 0110. --> 01100 --> 01100
            0101. --> 
                                    ^-- Elimination

Simple Search

A path (or search) is made by adding one set S at a time to make a group of sets G. After each addition, the permutation database D contains all of, and only, the allowed permutations for logic G.

Code: Select all

choose_first_set();
loop{
    choose_next_set();
    add_next_set();
    }

The permutation database D can grow exponentially or shrink depending on which sets are added. Each line in the database is equivalent to a branch in a search tree.

A set with M candidates that does not not overlap any candidates in the database will generate N new permutations for each permutation in the database.

A set that overlaps most or all candidates in the database can reduce the size of the database or even eliminate all permutations in the database.

Choosing the Next Set

The most important part about choosing the next set is to keep the number of permutations low, and there are several ways to do this. If D is the database, M is a bit mask of candidates in D, and X is a bit mask of candidates for the set under test.

Code: Select all

Check all remaining sets to find a minimum or a maximum values of (choose one):
   1.  M (and) X,   ... the maximum bits that overlap 
   2.  (not)M (and) X,  ... the minimum bits that do not overlap, 
   3.  D(perm add)A,  ... the minimum number permutations generated by adding A to D.
   4. (other ways), ... anything the helps minimize the no. of permutations in D.

Method.3 works well but is time consuming. The add_set() procedure used for addingc can be changed to count new permutations would be generated, but not generate them or change the database.

Starting a Set to solve a puzzle

The basic solver is like a logic machine, what comes out depends on what goes in. A basic set with n candidates contains one true candidate and n-1 false candidates. Thus, starting a whole set guarantees that a solution is in the database. Below, candidate A is true in the solution.

Code: Select all

{A,B,C} ---->
set     permutations          possible results
--------------------------------------------------------------
ABC     ABCDEFGHIJKL...
100 --> 100XXXXXXXXX... ---> 1001100011010... (the solution)
010 --> 010XXXXXXXXX... --->   <n=0>          (no perms)
001 --> 001XXXXXXXXX... --->   <n=0>

Starting a Set to find a contradiction

Eliminations occur long before the puzzle is solved. Any candidate whose column becomes all zeros can be eliminated becasue that candidate cannot be 1 in the logic.

Code: Select all

{A,B,C} ---->
set     permutations          possible results
--------------------------------------------------------------
ABC     ABCDEFGHIJKL...
100 --> 100XXXXXXXXX... ---> 1001XXX0XX0X...
010 --> 010XXXXXXXXX... ---> 0100XXX0XX0X...
001 --> 001XXXXXXXXX... ---> 0010XXX0XX1X...
                                    ^------- elimination

Starting a single candidate

The search process can be started with any logic including a single candidate vector or a single candidate. The results depend on whether the initial candidates are true of false. Again A is true and B is false.

Code: Select all

A is true:

set     permutations          possible results
--------------------------------------------------------------
ABC     ABCDEFGHIJKL...
100 --> 100XXXXXXXXX... ---> 1001100011010... (the solution)
or
1   --> 1XXXXXXXXXXX... ---> 1001100011010... (the solution)

B is false:

set     permutations          possible results
--------------------------------------------------------------
ABC     ABCDEFGHIJKL...
010 --> 010XXXXXXXXX... ---> <n=0>
or
 1  --> X1XXXXXXXXXX... ---> <n=0>

Starting a false candidate eventually leads to the addition of a set, Sn, that results in zero permutations. In this case, the database contradicts set Sn, i.e., for example the columns for candidates in Sn may = {000}.
.
.Edit: fixed X-Wing example.
.Edit: removed the term node in favor of the term candidate.

[champagne]

Hi Allan,

I just started reading your post. A very general but I think, very important remark.

You are using the word "Node" in place of candidate. As "node" is in your vocabulary a "cell"(I guess to have the shorts NRCB), this is source of trouble .

I will not be caught a second time, others could be.

champagne

[Allan Barker]

You are using the word "Node" in place of candidate. As "node" is in your vocabulary a "cell"(I guess to have the shorts NRCB), this is source of trouble .

Sorry, this is the first I know of this. My own way of thinking.....

R is a row
C is a column
B is a box
C is a (oops) can't use C for cell....
N is a cell with digits 1 through N, or possibly 'N'umerical

I (try) to use node only for a candidate in some logic structure
I would not use N for node.

I am flexible and happy to comply to what make sense.

[champagne]

Choosing the Next Set

The most important part about choosing the next set is to keep the number of permutations low, and there are several ways to do this. If D is the database, M is a bit mask of nodes in D, and X is a bit mask of nodes for the set under test.

search remaining sets for:
1. M * X = maximum nodes that overlap
2. notM * X = minimum nodes not already in D
3. A(perm)D = minimum number permutations generated by adding A to D. (time consuming, works good)

The key point for me at the moment. Let me check if I got it and tell you How I intend to use it.


The first step is clearly to have a start. Let say a set whatever is the way to choose it.

Then, you have a process leading to only one group following the here after guidelines :

1) select all sets having the highest number of candidates already in.
2) you say {if not 1)}. Iguess it means {if 1) gives several possibilities}.
I can not imagine that are remaining only sets not connected to existing Group in that process.

So I woud say, in the former selection, take those having the smaller number of candidates in excess.

3) With remaining sets, Test the arrangement and take the smaller number of permutations.

Step 3 must be done anyway to see whether the new group is "active".
Immediate question: what if we have still more than one set to choose, but I can imagine that you take anyone of them.

Next question: when do you give up if nothing appears? Is it a progressive search or do you go immediatly to big numbers (say up to 50 sets for example).

Still a question. The "active" group we get has no reason to be minimum. A "slim fast" program should still be applied. Is it done automatically in your process or is it something you do yourself.


Ho do I think to apply it.

If I take our example of FM floors 136 (forget rookery). We have in a "focusing step" found a list of about 16 candidates to clear. Each set bearing these candidates is a possible start. So we would have a limited number of starts.

Normally, we should try all of them to select the "best first action"


No urgency. I have enough to do to draft that process.

and thanks a lot

champagne


ps:

When the addition of set Sn results in zero permutations then set Sn contains a contradiction, i.e., Sn = {000}, etc.

I guess no solver to-day works on a non valid puzzle, so,

. any group of set have at least one permutation
. increasing the group size, you always finish with
all sets in
on permutation
and all invalid candidates in a zero state.

[champagne]

You are using the word "Node" in place of candidate. As "node" is in your vocabulary a "cell"(I guess to have the shorts NRCB), this is source of trouble .

Sorry, this is the first I know of this. My own way of thinking.....

R is a row
C is a column
B is a box
C is a (oops) can't use C for cell....
N is a cell with digits 1 through N, or possibly 'N'umerical

I (try) to use node only for a candidate in some logic structure
I would not use N for node.

I am flexible and happy to comply to what make sense.

I understand that you can find the word "candidate" slightly to limited in your wider scope, but for nearly all of us, it will take years before we get out of that limited view of set=row,column,box or cell/Node and candidates.

So If I had to sell your package, I would stick to the word candidates as long as possible, but I can survive with any choice you will make.

champagne

[Allan Barker]

You are using the word "Node" in place of candidate. As "node" is in your vocabulary a "cell"(I guess to have the shorts NRCB), this is source of trouble .

Sorry, this is the first I know of this. My own way of thinking.....

R is a row
C is a column
B is a box
C is a (oops) can't use C for cell....
N is a cell with digits 1 through N, or possibly 'N'umerical

I (try) to use node only for a candidate in some logic structure
I would not use N for node.

I am flexible and happy to comply to what make sense.

I understand that you can find the word "candidate" slightly to limited in your wider scope, but for nearly all of us, it will take years before we get out of that limited view of set=row,column,box or cell/Node and candidates.

So If I had to sell your package, I would stick to the word candidates as long as possible, but I can survive with any choice you will make.

champagne

I was missing the fact that Node is the accepted term for a cell. It is also the proper term for a connection point.

There is an old saying (which I create as I write). Saying what you want to say and saying what you want others to hear are not the same.

Let me think what to do.

[champagne]

I was missing the fact that Node is the accepted term for a cell. It is also the proper term for a connection point.

There is an old saying (which I create as I write). Saying what you want to say and saying what you want others to hear are not the same.

Let me think what to do.

I don't say "node" is an agreed term for a cell, but I made immediate assimilation reading your texts between "N" for a cell and implicit alternate name "node" I red.

This contributed certainly to the fact that I understood first "permutation" as exchange of rows colums and cells.

Once you are misleaded, all become very confusing.

But maybe I am alone having faced that problem, and I have now solved it.
champagne

[ronk]

I was missing the fact that Node is the accepted term for a cell. It is also the proper term for a connection point.

I don't say "node" is an agreed term for a cell ...

Oh, but it is, at least when the cell contains candidates rather than a given or a placement. From Jeff's rather well-known Forcing chains: Terminology and Definition thread ...

Node - a cell or a group of cells joining 2 links in a chain propagation. A node is multi-valued and may contain any number of candidates.

Curiously, the node term is not listed on sudopedia.org.

[Pat]

Node

A node is an item in a chain or loop. It can be a cell, a candidate or a complex structure like an Almost Locked Set.

The nodes are connected with links or edges.

[Allan Barker]

From Jeff's rather well-known Forcing chains thread ...
Node - a cell or a group of cells joining 2 links in a chain propagation. A node is multi-valued and may contain any number of candidates.

After reading Jeff's definitions, I agree with Champagne that the two uses of node could be confusing. I have replaced node with candidate in the above post.

After reading Pat's quote from Sudopedia, I see my use of node was OK but I will leave the term as 'candidate' to be safe.

.

[ronk]

Node

A node is an item in a chain or loop. It can be a cell, a candidate or a complex structure like an Almost Locked Set.

The nodes are connected with links or edges.

That's nice, but when Node is not on the Terminology index page here ... very few will ever see the definition. Besides, I take issue with Node being used for a single candidate ... primarily because it disagrees with Jeff's definition.

[Pat]

but when Node is not on the Terminology index page
... very few will ever see the definition.

yes, SuDoPedia does have some problems
-- e.g. the "Terminology" page was manually created as a separate article
where it should've been a Category (i.e. automatical).

i even noticed one term -- subset -- which appears twice in the list
(the 2nd time is out of alphabetical order)

[David P Bird]

As an AIC puritan I consider a node to be a Boolean condition that can either be true or false which can be linked by inferences (but I'll accept edges).

Hence we can have several types of nodes one of which is a single candidate (along with group nodes, almost patterns etc). It makes no sense to say a candidate is not a node, as it unnecessarily complicates defining the rules we use.

Ronk, in my eyes Jeff's definition is not the best

Node - a cell or a group of cells joining 2 links in a chain propagation. A node is multi-valued and may contain any number of candidates

The "multi-valued" description is fuzzy - in AICs a node is true or false, but Jeff wording seems to imply the node can have different values depending on which candidate in a group node is true.

"and may contain any number of candidates" seems to indicate that this includes the case when there is just one.

I don't want to start a war between Nice Loop and AIC users here, and my knowledge of the finer point of Nice Loops is decidedly limited, but surely there must be a way to harmonise the usage of this term.

BTW this interpretation makes a "kraken node" something of a misnomer as strictly speaking it's a set which is known to contain one truth either at most or perhaps at least.