Mike,
It seems we've reached an interesting point.
Recalling that both sets of rules can solve almost any minimal random puzzle and about 97% of top 1465, we have:
- an example of a situation (obtained from puzzle #3 ) in which no nrczt-chain can be found but Grouped NLs can,
- an example of a situation (obtained from puzzle #113 ) in which no Grouped NL [subject to the restrictions on size you mentionned] can be found but nrczt-chains can,
- an example of a situation (obtained from puzzle # 77) in which none of these can be found.
You said Carcul solved #77. I couldn't find his solution. Do you have any idea of what technique he used?
Fully supersymmetric chains
by denis_berthier » Sat Feb 02, 2008 8:01 am
- denis_berthier
- 2010 Supporter
- Posts: 4235
- Joined: 19 June 2007
- Location: Paris
by Mike Barker » Sat Feb 02, 2008 2:23 pm
The solution is of the toughest known puzzle. A quick look indicates that he uses multi-implication grouped nice loops with almost everything (AURs, almost fish, almost nice loops).
- Mike Barker
- Posts: 458
- Joined: 22 January 2006
by Mike Barker » Sat Feb 02, 2008 4:18 pm
That's not quite true. As I recall the Easter Monster requires multiple wrong propositions to create a contradiction. In the case of #77, I could plug it into Sudoku Explainer and get a solution using dynamic (+) forcing chains. The distinction is whether the chain is static (what is) or dynamic (what may be, trial and error). I haven't checked Carcul's solution to see what he used, but the goal would be to find a solution that is non-assumptive. The ultimate goal is to find a solution which uses some clever approach to simplify the solution.
- Mike Barker
- Posts: 458
- Joined: 22 January 2006
by denis_berthier » Sat Feb 02, 2008 4:26 pm
Mike Barker wrote:The solution is of the toughest known puzzle. A quick look indicates that he uses multi-implication grouped nice loops with almost everything (AURs, almost fish, almost nice loops).
Thanks for the reference.
Instead of such grouped-NL-nets, I should have nrczt-nets. Would it be enough for this puzzle? As I haven't programmed them (and I don't have much motivation for dealing with the most general nets), I can't tell.
I agree with your answer to Coloin, in the following sense: there seems to be ring patterns that are not nets with a single root (at least not obviously). But can we speak of multiple wrong propositions in this case? There is a global pattern to be found and no proposition to be assumed.
BTW, I programmed (my interpretation of) Steve's ring and checkedthat is produces the right eliminations on EasterMonster. Does anybody have another example xhere this rule applies?
- denis_berthier
- 2010 Supporter
- Posts: 4235
- Joined: 19 June 2007
- Location: Paris
by ronk » Sat Feb 02, 2008 8:33 pm
denis_berthier wrote:Does anybody have another example xhere this rule applies?
Fourteen of Ocean's puzzles with this property are posted here. Their Sudoku Explainer ratings vary from 9.5 to 9.9.
- ronk
- 2012 Supporter
- Posts: 4764
- Joined: 02 November 2005
- Location: Southeastern USA
by denis_berthier » Sun Feb 03, 2008 7:52 am
Mike, Ronk,
Thanks for the references.
I've checked that my version of Steve's ring applies in the 14 puzzles in Ocean and the 3 identified by Champagne in gsf's list.
I need some time to finish translating into plain English the formal logic definitions I use before I post them in a few days (in the other thread, because they are not chains).
Thanks for the references.
I've checked that my version of Steve's ring applies in the 14 puzzles in Ocean and the 3 identified by Champagne in gsf's list.
I need some time to finish translating into plain English the formal logic definitions I use before I post them in a few days (in the other thread, because they are not chains).
- denis_berthier
- 2010 Supporter
- Posts: 4235
- Joined: 19 June 2007
- Location: Paris
by coloin » Sun Feb 03, 2008 12:02 pm
I think steve would prefer the term sk-loop
[rather than "ring"]
I got the impression that it was widespread in the puzzles derired from the 16clue tempate which EM was produced from here
Thanks for the explanation on the incorrect assumptive clue[s].
C
[rather than "ring"]I got the impression that it was widespread in the puzzles derired from the 16clue tempate which EM was produced from here
Thanks for the explanation on the incorrect assumptive clue[s].
C
- coloin
- Posts: 2502
- Joined: 05 May 2005
- Location: Devon
by denis_berthier » Sat Feb 09, 2008 10:46 am
ronk wrote:Fourteen of Ocean's puzzles with this property are posted here. Their Sudoku Explainer ratings vary from 9.5 to 9.9.
As I was writing about nrczt-nets in the other thread, I've been distracted from this topic, but I haven't forgotten. I couldn't find these 14 puzzles among Ocean's full list of 411. Are you sure they come from this list?
(Or they may have been normalised. In the full list, they all start with a "0", whereas these 14 all start with a 1. I tried to find a normalisation software to check this but I couldn't.)
- denis_berthier
- 2010 Supporter
- Posts: 4235
- Joined: 19 June 2007
- Location: Paris
by denis_berthier » Sat Feb 09, 2008 11:10 am
coloin wrote:I got the impression that it was widespread in the puzzles derired from the 16clue tempate which EM was produced from here
As I understand it, all these puzzles are more or less the same wrt Steve's pattern (only candidates in cells outside the pattern may be different). Am I wrong?
coloin wrote:Thanks for the explanation on the incorrect assumptive clue[s].
Much has been said about assumptiveness but I can't make any sense out of it - except that it is just another name for T&E.
The problem is that the difference between a resolution rule and T&E is not yet clearly understood by everyone.
When a candidate can be eliminated by spotting a SINGLE well defined pattern (be it a Quad, an xy4-chain, an nrczt12-chain, …) in a grid and applying the corresonding well defined resolution rule, there is no T&E - however complex the pattern may be. This is because, in this case, no assumption is ever made, only some "static" or "factual" configuration of cells and candidates has to be found in the grid.
When the elimination of a candidate C obliges one to suppose it is true and to apply successively SEVERAL rules before he gets a contradiction on C, then this is T&E. I gave an example of T&E with my solution for EM. There, eliminating three candidates obliged me to write a full page of different rules for each of them. It is highly unlikely that any such sequence of rules could be replaced by the application of a single one.
So the difference may be stated as:
- not T&E: one step (one elimination) = ONE rule
vs
- T&E: one step (one elimination) = a SEQUENCE of rules.
Things are thus very clear when we speak in terms of logic and resolution rules. But when one thinks in terms of algorithms, everything gets mixed up.
- denis_berthier
- 2010 Supporter
- Posts: 4235
- Joined: 19 June 2007
- Location: Paris
by coloin » Sat Feb 09, 2008 1:16 pm
There is no doubting which is the more elegant way....
Overestimating I now realize. It is easy to find two wrong clues which scupper the "puzzle" by very simple techniques.
Sudoku Explainer finds and rates assumptive solution paths.
Here
I say Sudoku Explainer is making a big mountain out of a molehill, maybe you can confirm this
C
Mike Barker wrote:As I recall the Easter Monster requires multiple wrong propositions to create a contradiction.
Overestimating I now realize. It is easy to find two wrong clues which scupper the "puzzle" by very simple techniques.
Sudoku Explainer finds and rates assumptive solution paths.
Here
I say Sudoku Explainer is making a big mountain out of a molehill, maybe you can confirm thisC
- coloin
- Posts: 2502
- Joined: 05 May 2005
- Location: Devon
by denis_berthier » Sat Feb 09, 2008 3:56 pm
About EasterMonster:
For one false clue (= simple or depth 1 T&E), any one I've tried required many steps before leading to a contradiction or it led to nothing. Moreover, even with three false clues that led to the assertion of a strong nrczt-backdoor, the final path to the solution remained complex.
I have no opinion on two wrong clues (= depth 2 T&E) leading to an easy contradiction and an easy solution. Can you give the two clues? It seems very likely there are 2 such clues for the contradiction part. But what I don't see is why you say it is easy to find them and then why this would lead to an easy solution. Related question: when we know the two clues together lead to a contradiction, how easy is it to decide which may be eliminated?
T&E is a whole family of algorithms (see the "concept of a resolution rule" thread), depending on which set of rules is used to prune the search.
AFAIK, SE uses T&E pruned by a lot of logic rules.
I think Champagne's algorithm works the same way: breadth-first search (instead of the usual depth-first) pruned by a lot of logic rules, with the assumptive part disguised under tagging, layers, fusion of layers, choice and all the algorithmic glue.
In this context, the rate of a puzzle is highly dependent on the rules used to prune the search. Based on Ruud's top 10,000, I've shown that nrczt rules completely change the rating landscape.
The most stupid rating would certainly be the computation time of an algorithm, especially one relying on massive T&E or tagging, for which humans and computers do not perform the same way. SE is smarter than this, as its ratings rely on the most complex rule needed to solve the puzzle. But, for levels where logic rules are not enough and some form of T&E is used, the rating is very unclear to me. Indeed, I don't understand at all what "dynamic forcing chain" means.
In the reference you're mentioning, you say "A re-look at the puzzle [EM] does show that the 3@r4c1 can be inserted with ultra-simple techniques",
but you don't say which ultra-simple techniques you're thinking of. (You may have said it before in the same thread, but I haven't read its 53 pages).
coloin wrote:It is easy to find two wrong clues which scupper the "puzzle" by very simple techniques.
For one false clue (= simple or depth 1 T&E), any one I've tried required many steps before leading to a contradiction or it led to nothing. Moreover, even with three false clues that led to the assertion of a strong nrczt-backdoor, the final path to the solution remained complex.
I have no opinion on two wrong clues (= depth 2 T&E) leading to an easy contradiction and an easy solution. Can you give the two clues? It seems very likely there are 2 such clues for the contradiction part. But what I don't see is why you say it is easy to find them and then why this would lead to an easy solution. Related question: when we know the two clues together lead to a contradiction, how easy is it to decide which may be eliminated?
coloin wrote:Sudoku Explainer finds and rates assumptive solution paths.
Here
T&E is a whole family of algorithms (see the "concept of a resolution rule" thread), depending on which set of rules is used to prune the search.
AFAIK, SE uses T&E pruned by a lot of logic rules.
I think Champagne's algorithm works the same way: breadth-first search (instead of the usual depth-first) pruned by a lot of logic rules, with the assumptive part disguised under tagging, layers, fusion of layers, choice and all the algorithmic glue.
In this context, the rate of a puzzle is highly dependent on the rules used to prune the search. Based on Ruud's top 10,000, I've shown that nrczt rules completely change the rating landscape.
The most stupid rating would certainly be the computation time of an algorithm, especially one relying on massive T&E or tagging, for which humans and computers do not perform the same way. SE is smarter than this, as its ratings rely on the most complex rule needed to solve the puzzle. But, for levels where logic rules are not enough and some form of T&E is used, the rating is very unclear to me. Indeed, I don't understand at all what "dynamic forcing chain" means.
In the reference you're mentioning, you say "A re-look at the puzzle [EM] does show that the 3@r4c1 can be inserted with ultra-simple techniques",
but you don't say which ultra-simple techniques you're thinking of. (You may have said it before in the same thread, but I haven't read its 53 pages).
- denis_berthier
- 2010 Supporter
- Posts: 4235
- Joined: 19 June 2007
- Location: Paris
by coloin » Sat Feb 09, 2008 5:31 pm
Thanks for your reply.
Everything you say is very interesting - and refreshing. I need a bit of time to think about the T&E rating !
In my exploratory path , mostly page 53, I was progressivly understanding what was happening. I started with the EM puzzle - to look at some of the 1770 pairs of "wrong" clues. Initially we thought 3 clues at least were needed but, depending on the arbitrary solving limit, a pair of wrong clues can be proved to be wrong - by the development of a constraint.
Initially I was looking for a pair of clues positions or loci for which the only pair which didnt give an eventual constraint was the correct clues. I havent found one yet, but I was hoping that one would turn up at a low "solving" level. I optimistically suggested that this might be a pair which a good look for a non assumptive technique might be found, but possibly unlikely.
I moved on to a a less difficult puzzle - at random picked this puszzle SE 9.3 with an initial clue insertion step also rated 9.3.
Taking a pair of clues I found easily a pair for which the only pair which didnt give a constraint was the correct pair...great I thought.
Here are the "puzzles" with the paired loci @r4c1 andr5c2
"Box contra" is box contradiction, "contra" is a contradiction with a solving path a bit longer - but doable with pms. I dont have a solver for "invalid" puzzles !
But It depends how hard you try to find the constraint with the solving level. [if the clue is wrong there wil be a constraint] So this above shows us an assumptive method to insert 2 clues.
Then I noticed that you can [easily, by making an single clue assumption] place a clue at r4c1 [A4].
Though it would be a long chain - its not difficult to propagate it. I used the word "ultra-simple" to mean "singles" and no more.
Certainly it is not 9.3 any more IMO
C
Everything you say is very interesting - and refreshing. I need a bit of time to think about the T&E rating !
In my exploratory path , mostly page 53, I was progressivly understanding what was happening. I started with the EM puzzle - to look at some of the 1770 pairs of "wrong" clues. Initially we thought 3 clues at least were needed but, depending on the arbitrary solving limit, a pair of wrong clues can be proved to be wrong - by the development of a constraint.
Initially I was looking for a pair of clues positions or loci for which the only pair which didnt give an eventual constraint was the correct clues. I havent found one yet, but I was hoping that one would turn up at a low "solving" level. I optimistically suggested that this might be a pair which a good look for a non assumptive technique might be found, but possibly unlikely.
I moved on to a a less difficult puzzle - at random picked this puszzle SE 9.3 with an initial clue insertion step also rated 9.3.
- Code: Select all
+---+---+---+
|..4|...|2..|
|...|7.5|...|
|1..|.4.|..6|
+---+---+---+
|.7.|5.9|.4.|
|..9|...|3..|
|.4.|1.3|.9.|
+---+---+---+
|6..|.5.|..1|
|...|3.7|...|
|..2|...|8..|
+---+---+---+ ED=9.3/9.3/8.9
Taking a pair of clues I found easily a pair for which the only pair which didnt give a constraint was the correct pair...great I thought.
Here are the "puzzles" with the paired loci @r4c1 andr5c2
- Code: Select all
..4...2.....7.5...1...4...6*7.5.9.4..*9...3...4.1.3.9.6...5...1...3.7.....2...8.. puzzle
..4...2.....7.5...1...4...627.5.9.4..19...3...4.1.3.9.6...5...1...3.7.....2...8.. contra
..4...2.....7.5...1...4...627.5.9.4..29...3...4.1.3.9.6...5...1...3.7.....2...8.. box contra
..4...2.....7.5...1...4...627.5.9.4..59...3...4.1.3.9.6...5...1...3.7.....2...8.. box contra
..4...2.....7.5...1...4...627.5.9.4..69...3...4.1.3.9.6...5...1...3.7.....2...8.. box contra
..4...2.....7.5...1...4...627.5.9.4..89...3...4.1.3.9.6...5...1...3.7.....2...8.. box contra
..4...2.....7.5...1...4...637.5.9.4..19...3...4.1.3.9.6...5...1...3.7.....2...8.. contra
..4...2.....7.5...1...4...637.5.9.4..29...3...4.1.3.9.6...5...1...3.7.....2...8.. contra
..4...2.....7.5...1...4...637.5.9.4..59...3...4.1.3.9.6...5...1...3.7.....2...8.. contra
..4...2.....7.5...1...4...637.5.9.4..69...3...4.1.3.9.6...5...1...3.7.....2...8.. allows a solution
..4...2.....7.5...1...4...637.5.9.4..89...3...4.1.3.9.6...5...1...3.7.....2...8.. contra
..4...2.....7.5...1...4...687.5.9.4..19...3...4.1.3.9.6...5...1...3.7.....2...8.. contra
..4...2.....7.5...1...4...687.5.9.4..29...3...4.1.3.9.6...5...1...3.7.....2...8.. box contra
..4...2.....7.5...1...4...687.5.9.4..59...3...4.1.3.9.6...5...1...3.7.....2...8.. box contra
..4...2.....7.5...1...4...687.5.9.4..69...3...4.1.3.9.6...5...1...3.7.....2...8.. box contra
..4...2.....7.5...1...4...687.5.9.4..89...3...4.1.3.9.6...5...1...3.7.....2...8.. box contra
"Box contra" is box contradiction, "contra" is a contradiction with a solving path a bit longer - but doable with pms. I dont have a solver for "invalid" puzzles !
But It depends how hard you try to find the constraint with the solving level. [if the clue is wrong there wil be a constraint] So this above shows us an assumptive method to insert 2 clues.
Then I noticed that you can [easily, by making an single clue assumption] place a clue at r4c1 [A4].
- Code: Select all
Logic is
PMs at r4c1 are 2,3,8.
If A4 is a 2 then.......A4 cant be a 2 "alt SE"= 1.5 [singles only - my 10 year old nephew could do it]
If A4 is an 8 then......A4 cant be an 8 "alt SE"= 1.5 [singles only - my 10 year old nephew could do it]
Therefore A4 is a 3
Though it would be a long chain - its not difficult to propagate it. I used the word "ultra-simple" to mean "singles" and no more.
Certainly it is not 9.3 any more IMO
C
- coloin
- Posts: 2502
- Joined: 05 May 2005
- Location: Devon
