The New Sudoku Players' Forum

[ronk]

The nrczt-braid rule is a resolution rule. T&E is an algorithm. Saying the 2 are the same thing is therefore meaningless.

A resolution rule without an algorithm to implement the rule is meaningless. When a rule can only be implemented with a T&E algorithm, then it's a T&E rule IMO ... and the distinction between rule and algorithm becomes meaningless.

Do you have a non-T&E algorithm to implement your nrczt-braid rule

[denis_berthier]

A resolution rule without an algorithm to implement the rule is meaningless. When a rule can only be implemented with a T&E algorithm, then it's a T&E rule IMO ... and the distinction between rule and algorithm becomes meaningless.
Do you have a non-T&E algorithm to implement your nrczt-braid rule

Interesting claims/questions.

Firstly, a resolution rule doesn't have to be implemented as an algorithm to be a resolution rule: as any logical formula, it has an intrinsic meaning, independent of how it is used.
The raison d'être of resolution rules is to be useable by humans.
Human players use resolution rules, but I don't consider them as computer programs or as implementations of these rules. And I wouldn't claim that when they are looking for a pattern, they behave algorithmically.

Secondly, if a resolution rule is implemented in a computer system, it doesn't have to be as an algorithm. In SudoRules, resolution rules are "implemented" in a very straightforward way: directly as the logical formulæ that define them. It is the job of the inference engine to find occurrences of their condition patterns and to apply their action parts. This is what we call declarative programming in AI. (For some details about how this works, there is a short article in Wikipedia: http://en.wikipedia.org/wiki/Inference_engine)

Thirdly, yes, there can be an implementation of nrczt-braids which is not the T&E algorithm. I'd say, the T&E algorithm is the worst implementation of braids in all respects - except computation time. I could have another implementation by relatively easy modifications of my nrczt-whip rules. I don't have time right now, but I may do it in an undefined future.
The question then is: what'd be the difference? It would allow me to have full control over these rules, e.g. to give them priorities. In particular, it would allow me to find the shortest braids at any point of the resolution process (as I do with my chain rules in my default strategy). It would also allow me to use them in lots of other strategies, without modifying any of them - facilities that no simple (and still efficient) modification of the T&E algorithm could provide.
Corrected: indeed, T&E is NOT even an implementation of braids, as it doens't output a braid. To get the associated braid, I have to do some additional manual work.

Finally, all this should be kept in the proper perspective. As I said when I defined braids and as shown by the results reported in my first posts here, braids are not necessary unless we have an exceptionnally hard puzzle (and in some of these cases, there may even be alternative rules). I think normal players shouldn't bother too much about braids or nets in general.

[aran]

Denis

ANY PUZZLE SOLVABLE BY T&E IS SOLVABLE BY NRCZT-BRAIDS

Any puzzle solvable is solvable by T&E (obviously).
So reference to T&E can be removed from your corollary, restated as :
ANY PUZZLE SOLVABLE IS SOLVABLE BY NRCZT-BRAIDS.
But this really ought to be written as
ANY PUZZLE SOLVED IS SOLVABLE BY NRCZT-BRAIDS
and then secondly as
ANY PUZZLE SOLVED IS SOLVABLE BY NRCZT-BRAIDS PROVIDED THEY CAN MAKE USE OF THE SOLUTION PATH OF THE SOLVED PUZZLE.

If you agree with the above, I would be interested to know whether you see now or ever any practical implementation of that, and from the theoretical point-of-view how you see that as useful or potentially useful.

[ttt]

Denis

ANY PUZZLE SOLVABLE BY T&E IS SOLVABLE BY NRCZT-BRAIDS

Any puzzle solvable is solvable by T&E (obviously).
So reference to T&E can be removed from your corollary, restated as :
ANY PUZZLE SOLVABLE IS SOLVABLE BY NRCZT-BRAIDS.
But this really ought to be written as
ANY PUZZLE SOLVED IS SOLVABLE BY NRCZT-BRAIDS
and then secondly as
ANY PUZZLE SOLVED IS SOLVABLE BY NRCZT-BRAIDS PROVIDED THEY CAN MAKE USE OF THE SOLUTION PATH OF THE SOLVED PUZZLE.

If you agree with the above, I would be interested to know whether you see now or ever any practical implementation of that, and from the theoretical point-of-view how you see that as useful or potentially useful.

Hmm...! IMO, that is not good for reply here, if you don’t like or can’t follow then no need to post like that. At least you should show us something better from you…

My English is not enough then I can’t follow all Denis’s post together his concept but something seem to the same way I solve puzzles…

ttt

[aran]

ttt
I don't see any "substance" to your message.
Which is not meant as a criticism : just that if people replied every time they didn't like a post, who knows there might be a traffic jam on the forum.

[DonM]

FWIW: My take is that when there is a fairly major language difference, with some posts it is difficult to measure whether they are really all that critical. In this case and in all fairness to Aran, I don't think he was trying to particularly provoke or, for that matter, really raise anything other than a fair question.

[denis_berthier]

The purpose of this post is to show how the T&E vs braid theorems can be used to evaluate the scope of different types of braids (which is also an upper bound for the scope of the corresponding whips).

References:
1) Given a resolution theory T, the procedure T&E(T) was defined in the first post of this thread: http://forum.enjoysudoku.com/viewtopic.php?t=6390.
Remember that it is the standard Sudoku T&E technique (which is not itself a resolution rule): it uses no guessing and it is not recursive (it has only one hypothesis at a time).
2) nrczt-whips were defined here and in the following posts http://forum.enjoysudoku.com/viewtopic.php?t=5591&postdays=0&postorder=asc&start=136
3) nrczt-braids were defined here: http://forum.enjoysudoku.com/viewtopic.php?t=5591&postdays=0&postorder=asc&start=150
4) Various other more elaborate forms of whips and braids were defined here: http://forum.enjoysudoku.com/viewtopic.php?t=5591&start=203
5) Finally, the most general whips and braids associated with any family of patterns were defined here: http://forum.enjoysudoku.com/viewtopic.php?t=5591&start=205


Let BI be the Basic Interaction rules.
Let SubsetRules2 be the set of resolution rules for (Naked, Hidden and Super-Hidden) Singles and Pairs (and, of course, ECP).
Let SubsetRules3 be the set of resolution rules for (Naked, Hidden and Super-Hidden) Singles, Pairs and Triplets (and, of course, ECP).
Let SubsetRules be the set of resolution rules for (Naked, Hidden and Super-Hidden) Singles, Pairs, Triplets and Quads (and, of course, ECP).

Theorem:
1) Any elimination that can be done by T&E(ECP+NS+HS) can be done by an nrczt-braid
2) Any elimination that can be done by T&E(ECP+NS+HS + BI) can be done by a hinged-zt-braid
3) Any elimination that can be done by T&E(SubsetRules) can be done by a zt-LS-braid
4) Any elimination that can be done by T&E(SubsetRules + BI) can be done by a hinged-zt-LS-braid
5) Finally, the general form: for any family of patterns FP with associated resolution rules, any elimination that can be done by T&E(FP) can be done by a zt-braid(FP)
(The converse of each part is obvious).


In the 2nd post of this thread, I mentioned that all the puzzles in a random collection of 1,000,000 could be solved by T&E(ECP+NS+HS) or equivalently by nrczt-braids.
As a result, puzzles that are not in the scope of nrczt-braids are extremely rare and if we want to compare the scopes of the 4 types of braids above, we can only do this on a collection of exceptionally hard puzzles.
The natural choice for this is gsf's colection of 8152 hardest.

I give these results for two reasons:
- they may help clarify through examples how the above theorems lead to scope estimations;
- they shed some very unusual light on the top level of the hierarchy, which, wrt the various types of braids considered here, appears to be drastically more homogeneous than suggested by the Q1 rating.

Remember that gsf's collection is ordered according to decreasing Q1 rating.
In the following table, the first column defines the sets of puzzles I consider: slices of 1000 or 500 puzzles, depending on variability of behaviour within the slice.
The following columns show how many puzzles of each slice can be solved using the braids mentioned in the second row or, equivalently, the T&E(FP) procedure based on the FP family of patterns in the first row.
What's noticeable is that there is almost no difference for the slices corresponding to puzzles with Q1 rating between 99408 (EasterMonster) and ~8800 (when you check this, beware that the slices have different numbers of puzzles, so that you may have to add 2 of them to get comparable slices of 1,000), after which there is a drastic change in behaviour.

Code: Select all

Nb of puzzles solved:

FP family............ECP+NS+HS.........ECP+NS+HS+BI..............SubsetRules+BI
Braids used..........nrczt-braids......hinged-zt-braids..........hinged-zt-LS-braids
1-500................0.................187.......................443
501-1000.............0.................178.......................460
1001-2000............0.................331.......................976
2001-3000............0.................251.......................953
3001-4000............1.................233.......................945
4001-5000............1.................333.......................930
5001-5500............47................348.......................500
5501-6000............434...............490.......................500
6001-7000............981...............1000......................1000
7001-8152............1152..............1152......................1152
Total................2616..............4505......................7859
Rest.................5536..............3647......................393


When the theory T in T&E(T) becomes more complex than ECP+NS+HS+BI, computation times are very long: Triplets and Quads are relatively rare patterns and, in order to find them, the T&E procedure must explore almost all the candidate hypotheses, sometimes several times (phase iteration). After puzzles solved by hinged-zt-braids are discarded, there remain ~3500 puzzles in the collection; for each of them, T&E must try between 500 and 1,500 auxiliary puzzles; this makes ~ 3 to 4 million puzzles to deal with using the rules in T.
 

Edited 10/25/08: changed the notation to zt-braid(FP) - instead of my old zt-FP-braid.

[denis_berthier]

Since I got the above results, I've been thinking of the reasons why they seem at such variance with the classical ratings. I think I now understand it.

Most ratings are based on the lengths of various types of chains.
On the contrary, the above classification according to the types of braids (or of the elementary patterns used in the equivalent T&E procedure) abolish any notion of length of the braids used.
We thus have two complementary views on complexity.

This also shows that an implementation of braids that takes their length into account can't be considered as mere T&E.

[denis_berthier]

something seem to the same way I solve puzzles…

I don't know exactly how you solve puzzles but there is one way easy of doing it, even for the hardest, based on the above theorems: apply all the rules you can until you're blocked. Then start T&E in successive auxiliary grids with hypotheses that "look promising", applying the same set of rules (or simpler ones) in each of these auxiliary grids.
When an auxiliary grid leads to a contradiction, transform its internal eliminations and assertions into a braid (or some other kind of net) that will do the same elimination.
When you first published a solution based on nets, I had the impression you were doing something like this.
Could you give some detail about the way you solve puzzles?

[Allan Barker]

Denis,

What's noticeable is that there is almost no difference for the slices corresponding to puzzles with Q1 rating between 99408 (EasterMonster) and ~8800 (when you check this, beware that the slices have different numbers of puzzles, so that you may have to add 2 of them to get comparable slices of 1,000), after which there is a drastic change in behaviour

.
An interesting set of data, however one piece that seems missing is the average size of the braids in each of the bands. Size could be anything from number of nodes (candidates) to number of required operations. Another piece that might be revealing is the average Q1 rating for each band. What is the shape of this curve?

Your basic observation is that the number of solved puzzles is not increasing over a range where Q1 is increasing. It could be that the 'size' of the braids is increasing with Q1 but not the percentage of puzzles they can solve.

This fixed percentage of unsolvable puzzles may not be so surprising. I have seen that some kinds of logical structures appear only above a certain level of difficulty. Such structures may block a particular method, which would also explain why the percentage of solved puzzles does depend on the method you use.

Although there would be different types of structures, the classic example would be the highly symmetrical loops in puzzles like Fata Morgana here, where the absence of bi-value sets stumps many solvers. Large, symmetrical loops appear only in puzzles above a certain difficulty level but once they do, probably only a fixed percentage of loops would lack bi-value sets. This percentage would arise from a random distribution of set sizes rather than the puzzles' overall difficulty.

The effect of these structures is clear. Although traditional T&E and Algorithm X like methods can quickly solve all puzzles, both methods required four times the effort to solve Fata Morgana than Golden Nugget.

If the braids are all the same size, then I'm stumped.

[denis_berthier]

Denis,

What's noticeable is that there is almost no difference for the slices corresponding to puzzles with Q1 rating between 99408 (EasterMonster) and ~8800 (when you check this, beware that the slices have different numbers of puzzles, so that you may have to add 2 of them to get comparable slices of 1,000), after which there is a drastic change in behaviour

.
An interesting set of data, however one piece that seems missing is the average size of the braids in each of the bands. Size could be anything from number of nodes (candidates) to number of required operations. Another piece that might be revealing is the average Q1 rating for each band.

What my results say is that, in the whole range Q1= 99048 to 8800, there is no major difference in the proportion of puzzles solved by braids of ANY length, for the 3 types of braids mentioned.
We thus have a very different perspective from those based on length.
Of course, if we re-introduce length, we'll find differences.

This fixed percentage of unsolvable puzzles may not be so surprising. I have seen that some kinds of logical structures appear only above a certain level of difficulty. Such structures may block a particular method, which would also explain why the percentage of solved puzzles does depend on the method you use.

All depends on what you call a logical structure. It is more or less obvious if length is an ingredient of the definition.
But, if a logical structure is an elementary pattern, chainable in some sense, then the results show the converse of what you're saying - for the BI and subset patterns.
With a given set of building blocks, you can solve the same proportion of puzzles in every complexity class defined by the number of building blocks used in braids.

It means there are two almost independent components of complexity: types of the building blocks + length of the braids built on them.

I too was very surprised when I found this. So surprised that I checked my T&E algorithm several times.

[Allan Barker]

It means there are two almost independent components of complexity: types of the building blocks + length of the braids built on them.

This is exactly the situation I pointed out with Fata Morgana where the lack of bi-value sets (in the solution paths) relates to "building block" and the size of the loops relates to the "length". Although solution size goes up with difficulty, the lack of bi-value sets in some puzzles' loops stumps many solvers. Thus, we 'see' two degrees of freedom in complexity.

However, as mentioned in the FM thread, the "illusion of Fata Morgana" is an illusion in itself. Its illusionary difficulty can only be observed with certain solving methods. The set-solver has no problems solving the puzzle thus Fata Morgana is really a conundrum.

-- If a puzzle has properties that make it more difficult for some solvers, is the puzzle more difficult?

I too was very surprised when I found this. So surprised that I checked my T&E algorithm several times.

I did exactly the same with FM.

[denis_berthier]

It means there are two almost independent components of complexity: types of the building blocks + length of the braids built on them.

This is exactly the situation I pointed out with Fata Morgana where the lack of bi-value sets (in the solution paths) relates to "building block" and the size of the loops relates to the "length". Although solution size goes up with difficulty, the lack of bi-value sets in some puzzles' loops stumps many solvers. Thus, we 'see' two degrees of freedom in complexity.

Said this way, I agree. And my results give some kind of measurement of this. Of course, I should complete them with results for braids built on additional elementary patterns. But as computation times grow very fast when elementary patterns get more complex, I need careful thinking before I do this.

However, as mentioned in the FM thread, the "illusion of Fata Morgana" is an illusion in itself. Its illusionary difficulty can only be observed with certain solving methods. The set-solver has no problems solving the puzzle thus Fata Morgana is really a conundrum.

Here I don't agree. You suppose there is some intrinsic measure of complexity. I think this is where the illusion is.
I always speak of complexity wrt to some predefined set of rules. If one add rules, the relative complexities of puzzles can be drastically changed.

[denis_berthier]

A remark on braids.

"almost-ing" is the standard way of including elementary patterns in chains: ALS correspond to subsets and hinges correspond to BI.

"zt-ing", which can be seen as a generalisation of "almost-ing", is the natural way of including elementary patterns in whips or braids.

[StrmCkr]

If one add rules, the relative complexities of puzzles can be drastically changed.

the complexity wouldnt change. the implmented rule would allow advancement to a more complted state.

a solver gets stumped when it reaches an impass of logic it doesnt recoginze ie.

Fm

uses set constraints of layers
reasons why other solvers take long time to solve is they are to check many many combinations until it hits one of the few sets that works.

where the set solvers use constraints of bivalue locals to confine the puzzle, leading to sets of sets
(paired paired constraints or
paired propgation... article to be published by me soon enough still buildign with assistance for understandiblity)
and solves releivtily quickly.

that is the rules diffrenation between the two.

complexity of the rules added

defines "degree of difficulty required"
co insided with the avialiblty of alternative options at each phase
befor implementation of a move leadign to the impass of each solver.(if there is one if not completion is atained)