The New Sudoku Players' Forum

[Allan Barker]

If I understand well your method, I have a much better ides Just take the full group of sets. You'll have only one "permutation" and in once
all candidates to keep
all candidates to clear.

This is in fact how I would 'solve' GN is a few seconds. I will do one better, you do not need all the sets if you "search" for a solution. And, as you have also pointed out, one obtains all the solutions to a puzzle (simultaniously) becasue each remaining permutation is a unique solution. However, one must still calculate the permutations one set at a time.

I have a somewhat old discussion about permutatons here: http://sudokuone.com/sweb/permute/permute.htm

1) defining subgroups,
2) looking for “arrangements of candidates” fitting the group according to SUDOKU rules, the so-called "permutation".
3) If possibilities of clearing, assignment appear , looking for the best “set/link sets” arrangements explaining clearings and assignments.

This is all correct if you replace "1)defining subgroups", with "1) looking for arrangements of sets". I think subgroups is just difference in terminology. Point 3 is not difficult because an exact "set" solution is already defined at this point.

Point 1 is a hidden key issue.....

Yes, there is a hidden key issue and your comments on point 3 identify it correctly.
The issue is that such problems can become astronomical. At this point it becomes all computational but the problem is not trivial, which to some extent opens a new story. As for the logic part we now see eye to eye.

[champagne]

Hi Allan,

Let’s purge immediately a small point on which I disagree

Point 3 is not difficult because an exact "set" solution is already defined at this point.
.

Assuming
1) the number of sets is not to large
2) the process to define the rank for each set is well defined (and understood).

You may be right

With a large number of sets, you still have multiple ways to combine them in set/link sets.

This is in fact how I would 'solve' GN is a few seconds. I will do one better, you do not need all the sets if you "search" for a solution.
.

Reading your post, I came to a point that maybe reflects exactly what you want to say here.


Let us start from a group including all the sets. We have only one permutation; it is “the solution” of the puzzle.

We likely can suppress several sets and still have only one solution. We than come to the minimal group(s) of sets bearing the “hard logic”.

Some questions come:

1) are there several “hard logic cores”
2) do the smaller groups leading to clearings/assignments belong to these “hard logic cores”.

If, as I would bet, as soon as you reach a status where you can end the puzzle with a sequence of singles you are out of the “hard core”, then the true group of active sets is far below 324.

20 known nodes -> about 70 (20*4 less redundancy) sets inactive.

30 digits in the final sequence -> about 30*3= 90 more inactive sets,

In total, nearly half of the sets could be eliminated form the search.

If I am right, one could imagine two strategies:

1) for relatively easy puzzles, looking directly for small groups leading to clearing/assigning patterns,
2) for hardest puzzles, a preliminary step reducing the count looking for inactive sets.


Maybe Allan has immediate answers to such thinking;

champagne

[StrmCkr]

champane:regarding the purposal that i sent you.

paired constraitnts, with complex varations.

dual paired etc.

they are directly steming from what is summerized here.

permutations:

i belive you can focus the search tree down to a few specic target cell.
(which i outlined via pm)

[champagne]

champane:regarding the purposal that i sent you.

paired constraitnts, with complex varations.

dual paired etc.

they are directly steming from what is summerized here.

permutations:

i belive you can focus the search tree down to a few specic target cell.
(which i outlined via pm)

Hi strmckr,

For sure things are boiling out of what you sent me and from Allan findings.

From your side, there is the focus on all forms of pairs. From Allan, the very specific logic of sets/link sets constructions.

"fata Morgana" solution pointed out the fact that I was missing some usefull cases of "pair handling" much simpler than what I am doing. I will publish in the "full tagging thread" a summary of that fact.

It does not mean that we can mix both logics. You can solve the puzzle using

. nets of AICs,
. sets / link sets rules
. development of pairs as I did here to check how I could find equivalent solution to loop2 of Allan in FM.

and surely others ways.

I am not 100% sure that extending my solver to missing pair handling I'll find equivalence to Allan loop1 in FM. I am sure for loop2, but relying on loop1.

To conclude, pair handling is more in the current scope of my solver and somehow, I had strong clues with our discussions to come to the conclusion I made studying FM loops.

Allan logic, as I already wrote, is somehow different. Sometimes, it will go faster than AIC's nets, sometimes, it will be reverse.

One problem will be to optimize the use of so different tools.

champagne

ps in FM, the only finding of my solver was #3r5c6. This does not come in Allan study. If you mix this and #(1&6)r5c46 (that you can find in my analyze of loop2), you have immediatly r5c4=3. This is an example of how you can improve a solution using both logics.

[Allan Barker]

Logic Simuation

Hi Champagne, first the set/linkset point, and a comment about simulation.

Let’s purge immediately a small point on which I disagree

Allan Barker wrote:
Point 3 is not difficult because an exact "set" solution is already defined at this point.

Assuming 1) the number of sets is not to large 2) the process to define the rank for each set is well defined (and understood). You may be right

With a large number of sets, you still have multiple ways to combine them in set/link sets.

Ok, I will agree because your main point is that assigning weak/strong sets can be a complex problem, in the mathematical sense. This is true, and multiple set/linkset assignments are possible. My comment was that in practice, this is not much of a problem.

One reason is that the solver has already found an exact set solution, which will conform to "some kind" of logic principle(s). If this logic is based on strong/weak links then their assignment is (mostly) predetermined. The FM loop-1 below is before any linkset assignments but you can already recognize most of the linksets because they have nodes unconnected to other sets.



In this case, the solver used alternating strong/weak sets because they most easily produced the elimination. If the solver finds a broken wing there will be no assignable linksets. I was surprised the first time I saw this and thought there must be a bug. In this case, the solver taught me something.

nicely done... about time some one grasps how i solve and understands what i can do manually

In this case, the solver found at least some of the principles that Strmckr has worked out for attacking monsters like EM, FM, etc., by hand.
Assuming that Strmckr is human .....

These two cases make good examples of how simulation software is often used so I suppose one could use the term Sudoku logic simulation. I.e., encode basic principles and see what it produces.

I will continue in the next post.
.

[Allan Barker]

Let us start from a group including all the sets. We have only one permutation; it is “the solution” of the puzzle.

We likely can suppress several sets and still have only one solution. We than come to the minimal group(s) of sets bearing the “hard logic”.

Some questions come:

1) are there several “hard logic cores”
2) do the smaller groups leading to clearings/assignments belong to these “hard logic cores”.

I don't know an exact answer but what you describe is what I believe to be true. There definitely are large chunks of 'hard' logic and it seems each elimination cuts away at these. Not sure there is one master hard logic group. What I have seen is there can be a minimum block of logic that must be solved along the solution path. I mentioned on my website (page about candidate vectors) this minimum logic block might be an interesting way to rate puzzles.

When I mention minimum or logic block size I usually mean the number of permutations rather than the number of sets, but they are related. Along a soltuion path, the number of permutations can go up or down.

If, as I would bet, as soon as you reach a status where you can end the puzzle with a sequence of singles you are out of the “hard core”, then the true group of active sets is far below 324.

Again, this is close to what I see (maybe I can stop writing posts and just read what you have to say ) By the time you can solve the puzzle with just singles, there is often just one permutation left. Those puzzles that drag on with many simple eliminations will have a few remaining permutations for a while.

20 known nodes -> about 70 (20*4 less redundancy) sets inactive.
30 digits in the final sequence -> about 30*3= 90 more inactive sets,
In total, nearly half of the sets could be eliminated form the search.

If I am right, one could imagine two strategies:
1) for relatively easy puzzles, looking directly for small groups leading to clearing/assigning patterns,
2) for hardest puzzles, a preliminary step reducing the count looking for inactive sets.

Ah, now I begin to see your full idea. I have not tried this but it would be easy to do so. If such a group of sets can be subtracted from the problem (initially), it would reduce the complexity and probably help everywhere.

Allan

[StrmCkr]

Ah, now I begin to see your full idea. I have not tried this but it would be easy to do so. If such a group of sets can be subtracted from the problem (initially), it would reduce the complexity and probably help everywhere.

this is actually quite easy to arrange.

hints for doing so are pruining sets of pairs.
that are noncomplaiant. (little to no information gained on a depth plane)

for me i go with pairs limited to a house on the same row.
prune from there.
each pair has either truths or false. seen by linked submapings of the inital grid.

meaning that you can either include that mapping or remove it from the search tree quickly.

Assuming that Strmckr is human

i am human

[champagne]

Hi Allan,

Back to the Idea of "hard core".

I think it was a false good idea unless you can make something specific out of it.

Each of the following groups sets has only one permutation valid:

all nodes,
all rows,
all columns.

None of them can be considered as a hard core.

I am starting tests on the "permutation process" and this came immediatly.

champagne.

[champagne]

Hi Allan,

Back to the concept of hard core.


Yesterday, I was in a bad mood after I saw that you have not “the hard core”.

There are still limited views of “hard core” that we can use.

Let us consider the floor of candidates of the same digits.

27 sets are covering that floor (at most).

Any clearing or assigning pattern is still visible in the full group of sets of that digit.

So, you can easily check using the 9 groups whether you have actions out of such patterns.

Reducing the number of sets seems to me easier to achieve than combining sets adding one at a time.

This also open the door to several limited strategies to fight in a multi digits pattern. I know you have a highly performing process to do it, all I could imagine till now leads to big numbers of possibilities.


Speaking of limited strategies, I am thinking for example of limiting the “assumed set cover” to sets having at most four candidates.

Champagne

Ps: I saw you have questions regarding T&E and your process. See it in another way.

Whatever is the way your computer finds such patterns, and forgetting hardest puzzles, your findings are of interest if they can be applied by human on a pattern basis. Players will sort in your results and take what seems of interest for them.

The rest is pure “brain masturbation”.


EDIT

I made a quick test on that file recently publisher by tarek

Code: Select all

2.......3.8..3..5...34.21....12.54......9......93.86....25.69...9..2..7.4.......1 tarek jellyfish

It starts by a Jellyfish ont he digit 7. That fish appears as expected in the full groups of sets of the digit "7"

[Allan Barker]

Champagne,

I have seen things that "look like" logic cores or other things that behave "as if" there is some kind of hard logic, but I say this only because 'hardcore' is a nice word or name.

It sounds like you have something more specic in mind and perhaps something with specific properies. Can you better describe your meaning of hard core logic?

This also open the door to several limited strategies to fight in a multi digits pattern. I know you have a highly performing process to do it, all I could imagine till now leads to big numbers of possibilities.

It does lead to very big numbers and there is no systematic way to avoid them, but I have found there are ways to work within limited goals, just like you talk about limited stratigies.

Using permutations and solving a puzzle with sets are the two biggest ideas behind the solver. In addition, there are a couple of procedures I found that are useful for dealing with the complexity. One is the choice of the next set in a sequence of sets. In a similar way, the preformance of Algorithm X depends on choosing the next step.

I think it would be best for me to describe the whole process including how to find eliminations and put it on my website. I might get it uploaded early next week.

Speaking of limited strategies, I am thinking for example of limiting the “assumed set cover” to sets having at most four candidates.

I have done similar things, its also useful to limit the number of permutations. It is my gut feel experience that paths using large(r) numbers of permutations are no so useful.

27 sets are covering that floor (at most).
Any clearing or assigning pattern is still visible in the full group of sets of that digit.

So, you can easily check using the 9 groups whether you have actions out of such patterns.

Reducing the number of sets seems to me easier to achieve than combining sets adding one at a time.

Edit:Addendum

If I understand your idea or at least the concept:
1. Evaluate a single digit layer, 27 sets, RCB, (high complexity)
2. Do it 9 times, (low complexity, linear problem)
3. Combine the 9 layers by the vertical cell (N) sets. (low/medium complex)

This greatly reduces the complexity with a small reduction in "solving power". This is similar to Strmckr's layered approach, which I also observed in several puzzles.

It might be easy to combine the 9 layers by adding the permutations for each layer.
.

[StrmCkr]

It might be easy to combine the 9 layers by adding the permutations for each layer.

512 combinations (per layer reduced by given restrictions) * n many layers ( minus layer restricitns (assingments)

i stay say go with a restiction approch of
bilocal clues contained in a box on the same row/columnn/ cells.

combined into layers of each plane. shows. the above with a limited choice of 2 outcomes per mutation.

[champagne]

Hi Allan and strmckr,

I keep that post as prepared although part of the content is overlapping edit of Allan in the last post and strmckr remarks. I add at the end a partial answer to strmckr.

It sounds like you have something more specific in mind and perhaps something with specific properties. Can you better describe your meaning of hard core logic?

Nothing really clear up to now, but some ideas.

1 when you have a group of sets leading to actions (clearings or assignments), you can add any set, the already found clearing will stay valid.
2) Reversely, you can check whether you have the minimal set trying to suppress sets one by one. If you still have the same actions. For sure, sets bearing actions must stay. At the end, you have a kind of “minimal set” for these actions
3) You still have the possibility at that point to find subsets leading to a reduced “actions capability”. If so, you go to one minimal subset per “reduced actions capability”.


I have no example of that (out of what you said regarding “Fata Morgana”, but this seems granted.

Starting from that and having in mind that blind search of “active groups of sets” is horrible, I am thinking of specific strategies.

A specific strategy should fit with the human capability to recognize patterns, but it is to early to include this as a constraint.


The overall strategy would be to test big groups of sets and to apply a “slim fast” program to come to smaller patterns. I will give numbers later.

“Fishy patterns”

The simplest test is to consider a “rookery” (I use the word mentioned by "ronk" as qualifying all candidates of the same digit). A “rookery” includes all “fishy patterns” if I don’t misuse that qualification (XWing, Swordfish… but also Turbots …)

Testing a rookery is some milliseconds work. You know immediately if there is something to do out of it. You have to test 9 groups to focus (if needed) on the “active rookeries”.

Any rookery is limited to 27 sets, so it will be easy to apply the “slim fast” program.



Multiple rookeries strategy

If we try to do more form here, we can apply a “focusing” strategy including full rookeries. Let see on three examples how I think it could work. First of all, a multi rookery should be limited to 5 rookeries, less if some digits are missing (half of the lot). We will see that I am thinking of testing 5 rookeries for EM first loop;

Bi rookery.

Assuming all digits have still candidates, we have 36 bi-rookery possibilities. The process would be the following:

1) includes both rookeries
2) Add all nodes having one or both digits
3) Test that situation
4) If “action”, start the “slim fast” program.

Alternatively, you could in priority test bi rookeries having bi value nodes of the two digits. This is very often in “easy” puzzles where chains are crossing rookeries.

Three rookeries

We have 84 possibilities in a blind mode search. It becomes significant, but still very small compared to a step by step blind search.

We have a good example of a three rookery loop with “Fata Morgana”. The process would be basically the same as for two rookeries. Here, we can have the temptation to add a filter to improve the logic, or to be closer of human players detection of interesting patterns. I see several possibilities:

- At least one ternary node having the three digits,
- At least n ternary nodes having the three digits
- At least two such ternary nodes belonging to the same unit.

I am convinced, but this will be my next test, that a test on Fata Morgana rookeriess 136 will give very good results.

Easter Monster.

EM is an interesting case. Your loop is limited to rookeries 1267. If I am looking for clues to study it, I see nearly nothing. Just one node having only these four digits.

We have 126 possibilities in a blind mode search with 4 or 5 rookeries. Still manageable.

If I had to consider filters, a 5 rookeries in EM would be more attractive. Complementary rookeries to 1267 is the rest of the EM SK loop. But we have a better incentive to consider that group due to four nodes that could be sets (N1,7 N3,9 N7,9 N9,7)

I suspect that we could extract another “active group of sets” using these rookeries as you did using “1267”.

That’s all for the time being.

Using permutations and solving a puzzle with sets are the two biggest ideas behind the solver. In addition, there are a couple of procedures I found that are useful for dealing with the complexity. One is the choice of the next set in a sequence of sets. In a similar way, the performance of Algorithm X depends on choosing the next step.

I think it would be best for me to describe the whole process including how to find eliminations and put it on my website. I might get it uploaded early next week.

That would be a good idea.

champagne


ps to Strmckr.

I think you shoul not be afraid whether this search is far from your way to focus on the interesting part of the puzzle.

First of all, the human logic is nearly impossible to apply as such.
Selecting the "appropriate strategy" as I said several times is meaningless if it does not fit with human behaviour. I am convinced that in several steps, we will be much closer to you.

Last but not least, I will restart the "supercandidate" implementation as soon as I have finished that attempt to understand how Allan logic works.

[ronk]

The simplest test is to consider a “floor” (I don’t re use the word layer to qualify all sets of the same digit because that word has another meaning in full tagging).

If your meaning is the pattern of all nine appearances of a single digit ... the proper term is rookery.

Floor already has a different generally-accepted meaning.

[champagne]

The simplest test is to consider a “floor” (I don’t re use the word layer to qualify all sets of the same digit because that word has another meaning in full tagging).

If your meaning is the pattern of all nine appearances of a single digit ... the proper term is rookery.

Floor already has a different generally-accepted meaning.

I edited my post in that way.

I had to use my dictionnary to find the meaning of "rookery". I have been surprised to learn that the best way to go fishing was to work on a colony of birds.

[ronk]

I had to use my dictionnary to find the meaning of "rookery". I have been surprised to learn that the best way to go fishing was to work on a colony of birds.

It might make more sense if ... you think of it as the birds doing the fishing