The New Sudoku Players' Forum

[gsf]

However in EM, I cant see more than approx. [60*4]^2 / 2 = 28800 proposition pairs.......

edit: after thinking more
the P constraint orders the propositions by degree (n-location/n-value), smallest order first
to mimic the usual "most constrained first" approach, and to wash ordering bias
so it may do more than #candidates^2/2 proposition pairs for harder puzzles
internally it keeps track of repeated propositions to avoid extra work
the high proposition counts (~100K) are hit when higher degree candidates are in play

[coloin]

Hmmm

Code: Select all

+---+---+---+
|1..|...|..2|
|.9.|4..|.5.|
|.46|...|7..|
+---+---+---+
|.5.|9.3|...|
|...|.7.|...|
|...|85.|.4.|
+---+---+---+
|7..|...|6..|
|.3.|..9|.8.|
|6.2|...|..1|
+---+---+---+

The EM "puzzle" with two extra wrong clues - is found to be invalid with simple methods.

Code: Select all

propositions  25009  solutions   0  contradictions   2  iterations  57110  girth   9  degree   3  nesting 2


I think it is unlikeky that this is the only one of two combinations which have this property - I must have interpreted wrongly !

The proposition counts higher than this must be when you consider 3 clues combinations, which is getting complicated...........over 2M !

C

[gsf]

Hmmm
The proposition counts higher than this must be when you consider 3 clues combinations, which is getting complicated...........over 2M !

P constraints only consider 1 or 2 at a time
but those 1 or two are chosen by degree order (n-value/n-location), so some may be examined more than once
(again, this is to mimic the natural "look at most constrained first", e.g., bi-value/bi-location)

assuming all singletons produce no contradictions,
then for pairs that do produce contradictions you can't tell which of either or both are bad
until all pairs for that degree have been checked
at that point verities can be also be checked on the inconclusive (no solution, no contradiction) pairs

[coloin]

I sort of see.....but there are still only 28800 pairs, and we do know which of these are {right,right}{right,wrong}{wrong,right}{wrong,wrong}and each of these pairs will give a result ofone of:
no contradictions
simple initial contradiction
simple contradiction furthur down the path

There are 60*59/2 paired loci. Given a pair of clues at a paired loci, if there is a contradiction - we can say that clue 1 AND clue 2 together are "wrong".

If [?] at one paired loci there is only one pair of clues with no contradiction - then these are the correct clues for the paired loci.

assuming all singletons produce no contradictions

this will not be the case in hard puzzles which have pearl ER rating 1.2....which is quite common. I suppose these hard puzzles need to be solved to a level and then proposition clues can be looked at.

All puzzles with pearl ER rating >~7 will not produce a contradiction with singletons [? by definition]

I was thinking as a rating technique, not a solution technique

Well we are thinking of a solution technique, but the ease of this solution/invalid solution is effectively a rating.

It is rating the puzzle from a T&E, assummptive standpoint...

but isnt this how these rating programs work:
suexrat9 [backtracking,node count]
Sudoku Explainer - this makes assumptions to confirm an elimination - " if B6 is a 3..<chain> .....then B6 is not a 3, therefore B6 is not a 3 ....!"

Standardizing/rating non-assumptive technigues is in the eye of the beholder. Maybe I would do well to try to understand a non-assumptive solution method !

C

[champagne]

Coloin wrote

Rating invalid "puzzles"

Well daj95376 did it .....here …

Daj answer is clear to me. First he establishes that six possibilities are remaining to fix all missing 6, then prove that 5 are wrong. This is the common way we are doing with kraken blossoms. As far as I could see, it is a little more sophisticated in daj example, because the six templates are not derived form a choice, but the philosophy is the same.

So I could say that all solvers are rating invalid puzzles.

You wrote

However.....
A combination of two incorrect cells would tend to make even the hard "puzzle" recognizably "invalid". ….

Out of all recent discussions, I have the feeling that I could answer very simply.

As long as you don’t use level 4 in tagging (or something equivalent), You have a set of candidates that can be cleared thru a net of AICs leading to the solution. This means likely that this set of candidates can be used in T&E mode. (I am not 100% sure due to the use of ALS AHS in the AICs.). At the end, the puzzle is solved.

If you have to use level 4 to crack the puzzle, then in the same way, you have a set of super candidates (two candidates belonging to an AC2) leading to the same conclusion. Choosing two candidates in that set in T&E mode should again lead to an invalid configuration.

I don’t know if this answers your question in case you think yes, I could look for examples

Regarding rating methods, anybody checking validity in T&E mode have in fact its own. I made again a quick comparison using the top list of tarek p48 in this thread. Difficult to find any correlation.

In the list, the fourth number is the time in milliseconds to check validity. (should be stable overtime with a program run alone, here in windows multi processing environment.) My process to check validity is a count of the number of solutions using T&E and basic rules. This forces to use the entire set of unknown candidates. (You have also the five puzzles of my sample file).

#tarek-191#95765#1254#692 47 7s281
coloin-04-10_02805 31 3s516
Easter Monster 31 25s547
# m_b_metcalf 46 20s375
Golden Nugget 109 115s812

tarek file

#018##95015#2318#1306 281 47s641
#032##98760#1890#1182 235 17s610
#031##95209#2331#1211 234 80s109
#029##96813#2002#1217 203 34s875
#001##95657#3464#2141 188 115s469
#010##95482#2252#1417 172 37s954
#045##92747#2002#1104 172 17s265
#004##67650#2552#1588 156 52s344
#015##95269#2694#1322 141 16s813
#003##95249#2868#1756 140 25s328
#005##99072#2511#1537 140 77s671
#023##95748#1903#1252 125 16s313
#024##95562#2773#1244 109 62s750
#016##60750#2385#1317 109 23s0
#014##95366#1854#1325 94 25s515
#020##91001#1980#1295 94 18s656
#021##98827#2014#1256 94 31s688
#002##70107#2953#1848 94 38s141
#034##95034#1881#1175 94 55s781
#028##67544#2001#1226 79 32s672
#008##95730#2278#1465 78 38s266
#011##28563#2071#1400 78 39s93
#012##73973#2142#1393 78 60s110
#013##96118#2012#1338 78 38s703
#017##98604#2050#1307 78 19s578
#019##95407#2119#1301 78 20s234
#025##95030#1844#1239 78 30s234
#027##97509#2016#1230 78 22s359
#030##95246#2036#1217 78 28s141
#036##94970#2025#1161 78 51s656
#038##95734#1838#1142 78 32s31
#040##95212#1807#1137 78 57s687
#043##95014#1880#1114 78 47s640
#044##96111#2083#1106 78 8s610
#006##95009#2283#1487 63 35s172
#007##95771#2324#1472 63 40s797
#026##98803#2039#1231 63 66s250
#041##95578#1855#1124 63 18s406
#009##95230#2054#1451 62 68s265
#022##95141#2228#1253 62 34s734
#033##95006#1814#1182 62 28s578
#035##87618#1994#1167 47 24s891
#037##95231#1901#1159 47 69s297
#039##95245#1863#1138 47 13s641
#042##95306#1855#1115 47 18s282


Difficult to find two sets correlated

[coloin]

Thanks for the reference to "kracken blossoms" - I didnt know that.....

Your data does confirm GN though which is a plus

I presume the time taken in milliseconds with easy puzzles is fairly short !

I didnt think T&E was envoled in your solver

Any method which makes a placement is valid - if you can find it. Non-bifurcationists would disagree.

I have looked briefly at the EM puzzle and I cant find a pair of clue loci [out of a total of 1770] which has only one pair which doesnt lead to a contradiction [ie the correct pair] [some do come fairly close]

Heres one

Code: Select all

+---+---+---+
|1..|...|..2|
|.9.|4..|.5.|
|..6|...|7..|
+---+---+---+
|.5.|9.3|...|
|...|.7.|...|
|...|85.|.4.|
+---+---+---+
|7*.|...|6..|
|*3.|..9|.8.|
|..2|...|..1|
+---+---+---+  pair loci at r7c2 & r8c1

1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7*....6..*3...9.8...2.....1

1.......2.9.4...5...6...7...5.9.3.......7.......85..4.71....6..43...9.8...2.....1  contra
1.......2.9.4...5...6...7...5.9.3.......7.......85..4.71....6..53...9.8...2.....1  contra
1.......2.9.4...5...6...7...5.9.3.......7.......85..4.71....6..63...9.8...2.....1  no contra [correct]
1.......2.9.4...5...6...7...5.9.3.......7.......85..4.74....6..43...9.8...2.....1  box contra
1.......2.9.4...5...6...7...5.9.3.......7.......85..4.74....6..53...9.8...2.....1  no contra
1.......2.9.4...5...6...7...5.9.3.......7.......85..4.74....6..63...9.8...2.....1  contra
1.......2.9.4...5...6...7...5.9.3.......7.......85..4.78....6..43...9.8...2.....1  no contra
1.......2.9.4...5...6...7...5.9.3.......7.......85..4.78....6..53...9.8...2.....1  no contra
1.......2.9.4...5...6...7...5.9.3.......7.......85..4.78....6..63...9.8...2.....1  contra

Easy puzzles will always have these "unique correct pair loci", which implies that hard puzzles wont have very many.

Is it possible to count up these unique correct pair loci.......?

Has this solving method got a name too ?

C

[champagne]

Just a quick answer where I can easily do it

I presume the time taken in milliseconds with easy puzzles is fairly short !

less than one millisecond for easiest ones

I didnt think T&E was envoled in your solver

T&E is by far the easiest way to count solutions in any puzzle. the quickest, as far as I could see requires use of basic rules (naked singles and locked set). I check validity before solving the puzzle without T&E mainly because I authorize use of Unique Rectangles clearings;

Any method which makes a placement is valid - if you can find it. Non-bifurcationists would disagree.

I am a Non-bifurcationist for sure, at least for the solver.

For the rest, I am to study your post.[/quote]

[coloin]

Indeed, I think for elegance you have to be superior.

In my defence I never ever like uniqueness

Has this solving method got a name too ?

a little thought, and jokingly I am going to guess its could be called "double dynamic forcing chains ?"

double - paired clues
dynamic - clues are guessed
forcing - the only paired clues [the correct ones] are forced

not sure how long the chain length is though !

But it is still similar to "Kraken Blossom" although this Sudoku Unification Model post suggests all these advanced methods are objectively very similar.

With the EM puzzle in mind, these are the possibilities.

1. If we can find a specific pair loci we have made two placements.

2. If we only find one pair loci - perhaps these are the pair loci where you can look for a non-assumptive technique.

3. If we cant find a pair loci then this could be coined an "inverse M3" although maybe gsf's M3 function goes this far already......but I dont think it does.

- whichever of these options apply - I think we have progressed.

C

[champagne]

After

Any method which makes a placement is valid - if you can find it. Non-bifurcationists would disagree.

And

I am a Non-bifurcationist for sure, at least for the solver

.

Coloin wrote

Indeed, I think for elegance you have to be superior

.


Let me tell it another way.

Using T&E, all has been said and written for long. (not that much to say indeed). The only challenging game is to find solving path not using T&E.

Same for those as you creating hard puzzles; the game exists only against non T&E process. By construction, no puzzle can resist to the T&E process. I am convinced than within some months a puzzle will appear resisting to my solver in to-day state.


Uniqueness is a marginal issue. You like it or not, it does not affect substantially the solutions. Sometimes, it provides shorter paths, often it gives clearings out of the scope.


Regarding double clues, I tried to apply it in EM to an AC2 belonging to the SK loop, r2c13. I got results very similar to yours. Seven possibilities, 3 have a quick end , for the three other False, Blockage came after a long way . This means that in T&E mode, one additional step with clues would be necessary sticking to basic clearing rules.

[gsf]

Using T&E, all has been said and written for long. (not that much to say indeed). The only challenging game is to find solving path not using T&E.

I disagree
and again I'm making a distinction between rating and solving
I don't believe a rating program must necessarily mimic method/technique base solving
just look at the fairly decent job suexrat* does, and it only uses singles

the problem with T&E is that it can be order dependent
so a rating based on T&E must somehow wash the ordering effect
one way is to average over multiple runs (suexrat* does this)

another is to follow all move possibilities and measure the work done doing that
but for hard sudoku all possibilities could be intractible

the P proposition constraint in my solver (specifically for rating puzzles) takes a conservative approach
it orders the guesses by candidate order (n-location/n-value) and does all of the
move possibilities by order, low to high, first singletons, then pairwise
(this is where the duplicates come in to exceed the N^2/2 estimate of the number of pairs)

as all the ideas on this thread, its a work in progress
the point is, re rating, T&E still has a place

[coloin]

We are indeed trying to rate the puzzles, you need to solve them first and then decide how difficult that was. Whiich is what we have been doing.....

It is challenging to find a solving path not using T&E, and I see you have looked at the clues in "region" of the SK-loop to see if there are a pair of clues which gives us a double placement.

It remains to be seen if there is a pair of clues [of the 1770 paired loci] in EM which will fulfil this criteria.

I am beginning to think they wont be there.

gsf's program doesnt appear to "see" the contadictions that we are seeing !

I am not sure which option [no pairs, one pair,several pairs] I am hoping to be found.

perhaps if we found a "hard" puzzle with only one pair then this is where we could direct champagne to look for a non-assumptive solution. I'm always optimistic !

I dont know how this affects how we rate puzzles, but it would be an advance in the work in progress.

It might be news to "Bill", "MythJ" and "DonM" too

C

[coloin]

Easy puzzles will always have these "unique correct pair loci", which implies that hard puzzles wont have very many.

This hard puzzle has one, the first one I looked at - from the patterns game.

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

Randomly I chose two paired loci ......r4c1 and r5c2

The pms in these two cells are 238 and 12568

The possibilities are

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

Therefore using this assumptive method we can say r4c1 is 3 and r5c2 is 6

Code: Select all

+---+---+---+
|..4|...|2..|
|...|7.5|...|
|1..|.4.|..6|
+---+---+---+
|37.|5.9|.4.|
|.69|...|3..|
|.4.|1.3|.9.|
+---+---+---+
|6..|.5.|..1|
|...|3.7|...|
|..2|...|8..|
+---+---+---+  SE 7.1, "fiendish"......possible by humans.

I dont know how many paired loci give placements in this puzzle. I would like to think the puzzle could be solved easily with other paired loci which give placements.

I dont think I have ever "solved" a 9.3 before.......

C

[champagne]

champagne wrote:

Code: Select all

Using T&E, all has been said and written for long. (not that much to say indeed). The only challenging game is to find solving path not using T&E.

gsf answered

Code: Select all

I disagree
and again I'm making a distinction between rating and solving
I don't believe a rating program must necessarily mimic method/technique base solving
just look at the fairly decent job suexrat* does, and it only uses singles

the problem with T&E is that it can be order dependent
so a rating based on T&E must somehow wash the ordering effect
one way is to average over multiple runs (suexrat* does this)

Several points in your answer.

1) T&E is often order dependent that's right. Counting possible solutions of a puzzle is not. So the time I gave is not order dependant.

2) Is counting of solutions a kind of rating ? I would say yes and no. It follows all move possibilities and processing time is one acceptable way to measure the work done doing that .
Why not?
I can accept without any problem that a rating intend to classify puzzles and to identify specific properties. This gives added value for sure.

For me the truth remains "how hard is it to solve it". If T&E is accepted, then counting process is an acceptable measure. If you try to solve the puzzle excuding T&E, then the reality is that we have a poor correlation between ranking in T&E mode and ranking out of T&E mode. Nobody can predict how hard it will be to crack a puzzle before he does it.


I understand that you have extended T&E analysis to pairs. OK, why not, but we are back to the fundamental question: why and what are we rating.

What is clear and in favour of your step is that some puzzles are requesting, as far as I could see some "pair" analysis.

If I consider your list of hard puzzles, most of the puzzles requesting my level 4 are in the first part of your list. But the first one is only ranked 03.... and some above 95000 do not need level 4 (pairs analysis).


Anyway when I said "Using T&E, all has been said and written for long."
It clearly refered to puzzles cracking. My counting procedure has been written years ago and I did not change one character in the coding.
You are working on puzzles structure using T&E procedure, this is quite another job.

[coloin]

Code: Select all

gsf's program doesnt appear to "see" the contadictions that we are seeing !

I now see why, because my view of the contradictions is set significantly higher.

Perhaps we need to turn the definition of "simple" up one notch...perhaps to the limit of my ability with a pencil.

I am wondering just how "difficult" those non-box contradictions are in the assumptive solution of the 9.3 puzzle............

A re-look at the puzzle does show that the 3@r4c1 can be inserted with ultra-simple techniques. So why is it 9.3 ? [Edit - or M2]

Alternative Sudoku Explainer..........
where [A4=r4c1] [pms are 2,3 or 8]

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

If A4 is a 2 then.......A4 cant be a 2   "alt SE"= 1.5
If A4 is an 8 then......A4 cant be an 8  "alt SE"= 1.5

Therefore A4 is a 3

I am going to have to think why SE is considering this placement to be so difficult !

The logic is no different IMO

C

[gsf]

I am going to have to think why SE is considering this placement to be so difficult !

because SE doesn't combine the results of its paired (double proposition) failures

I believe (but can't confirm) that SE's double forcing ... methods assert 2 candidates
and then determine where the resulting chains lead -- if they lead nowhere then the
2 asserted candidates are retracted

here's how the P constraint method (again, T&E for rating) does paired propositions
recall that a degree d tuple is a collection of d-location/d-value candidates
e.g., degree 2 == bivalue/bilocation

Code: Select all

for degree D in 2 .. max-degree
  for all tuples T of degree D
    for all candidates C in tuple T
       copy the grid
       assign candidate C
       for each remaining candidate R in tuple T
         copy the grid
         assign candidate R
         solve using the constraints in scope (ususally singles with optional locked-candidates)
       if none of the assignments R ... led to a solution
       then C is inconclusive
       else if all of the assignments R ... led to a contradiction
       then eliminate C (this is a paired proposition contradiction)
       else if any of the assignments R ... led to a solution
       then assign C (this is a paired proposition solution)


for efficiency the implementation keeps track of tests already done (some candidates may be in more than one tuple)

this basically models an ordered (by degree) backtrack tree search that follows all possibilities for each degree;
by looking at all possibilites by degree the ordering effects of lucky guesses (and lucky pruning) that hamper suexrat* are washed

you can use my solver to play with e.g. the recalcitrant candidates in easter monster

Code: Select all

sudoku -v2 -X -q'FNBP*-G' 100000002090400050006000700050903000000070000000850040700000600030009080002000001

[1]      propositions   5390  solutions   0  contradictions   1  iterations  10748  girth  15  degree   3  nesting 2
     P1  [31]^2
         propositions   5782  solutions   0  contradictions   1  iterations  11541  girth  15  degree   3  nesting 2
     P1  [13]^7
         propositions  90964  solutions   0  contradictions   2  iterations 227574  girth  17  degree   4  nesting 2
     P1  [85]^4
         propositions 134350  solutions   0  contradictions   2  iterations 345353  girth  17  degree   5  nesting 2
     P1  [26]^8
         propositions 166693  solutions   0  contradictions   2  iterations 430159  girth  17  degree   5  nesting 2
     P1  [59]^6
         propositions 175893  solutions   0  contradictions   0  iterations 455176  girth  17  degree   6  nesting 2
1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1 # 98784 no-solution no-solution


the P1 lines following the nesting 2 lines show the weak part(s) for the degree in scope
the first one is [31]^2 (add -Fp'r%rc%c' -Fn'<>' to get r3c1<>2)
this means that [31]=2 (r3c1=2) is inconclusive w.r.t. the constraints in scope (FNB == singles + locked-candidates)
you can verify this by

Code: Select all

sudoku -v2 -qFNB-G 100000002090400050006000700050903000000070000000850040700000600030009080002000001 31=2

[1]  N1  [13]=5
         box-line 3 b/2    [24][25][26][27][28][29]
         box-line 4 b/2    [42][52][62][72][82][92]
     B6  [25][27][29]^3 [52][72][92]^4
1.......2.9.4...5.2.6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1 #     6 no-solution no-solution