dobrichev, my understanding is that fuss2 always works with bivalve cells for T&E. In the text you quoted, I was talking about using using bi-located candidates instead, houses that only contain two instances of pencil marks for a specific digit.
I am well aware of the advantages of pesudo-random choices over topmost choices. If you go back and look closely at the history of the various fast brute force solvers you will find that I was the first one to introduce a version of that particular optimization.
Puzzles Usage in a Presentation of a New Rating of Puzzles
Re: Puzzles Usage in a Presentation of a New Rating of Puzzl
by JasonLion » Sun Mar 01, 2015 1:22 pm
-
JasonLion - 2017 Supporter
- Posts: 642
- Joined: 25 October 2007
- Location: Silver Spring, MD, USA
Re: Puzzles Usage in a Presentation of a New Rating of Puzzl
by eleven » Sun Mar 01, 2015 3:59 pm
Since i was curious, how much better i could be than the average rating, using the same T&E strategy, but with "intelligent" selection of the T&E numbers, i made a test with Golden Nugget, using a solver which i allowed singles, locked candidates and subsets.
The result was quite disappointing (ok, i am not the best solver, and i was impatient soon from the tedious work):
I needed 62 guesses, compared to the 82, blue had calculated with 3-way guesses at the beginning.
What i tried to improve was to only take pairs of candidates, which in both cases would give me numbers, in order to assure, that each guess would make some progress.
At the beginning this was not possible, so i decided to take the pair with the most eliminations on both sides. Also later there was a situation, where in all cases at least one side produced a number.
I also tried to avoid to make a guess for digits, which only produce one more in an empty x-wing or 2 in a 6-cell pattern, but nothing else.
Pairs don't seem to be that bad, if they only share one house (not both a box and a line).
So i don't expect much better ratings for very hard puzzles now with bilocal candidates, probably it is better to combine them with the bivalues. Excluding 2-house-pairs, empty x-wings and 6-cell-patterns might make it slightly better.
In some puzzles of course the difference to blue's average rating will be much bigger (as i saw with the 17 clue sample).
The result was quite disappointing (ok, i am not the best solver, and i was impatient soon from the tedious work):
I needed 62 guesses, compared to the 82, blue had calculated with 3-way guesses at the beginning.
What i tried to improve was to only take pairs of candidates, which in both cases would give me numbers, in order to assure, that each guess would make some progress.
At the beginning this was not possible, so i decided to take the pair with the most eliminations on both sides. Also later there was a situation, where in all cases at least one side produced a number.
I also tried to avoid to make a guess for digits, which only produce one more in an empty x-wing or 2 in a 6-cell pattern, but nothing else.
Pairs don't seem to be that bad, if they only share one house (not both a box and a line).
So i don't expect much better ratings for very hard puzzles now with bilocal candidates, probably it is better to combine them with the bivalues. Excluding 2-house-pairs, empty x-wings and 6-cell-patterns might make it slightly better.
In some puzzles of course the difference to blue's average rating will be much bigger (as i saw with the 17 clue sample).
- eleven
- Posts: 3097
- Joined: 10 February 2008
Re: Puzzles Usage in a Presentation of a New Rating of Puzzl
by eleven » Sun Mar 01, 2015 9:14 pm
There is an alternative method to attack very hard puzzle with newspaper techniques, also mentioned by mollwollfumble.
You choose a line with say at least 5 unsolved cells, which does not allow too much permutations. Then go through them one by one.
I always wanted to know, if it's better or worse than the 2-way-guesses.
So i started to do the next tedious session, and tried Nugget with this method, again using locked candidates and subsets (the newspaper techniques).
I choose column 5 and got 35 possibilities, 18 remained after applying the techniques (the others all leaded directly to a contradiction).
For only 2 of the 18 i made more than one guess then, for one 4, the other 2 (skyscraper would save at least 2 guesses).
This sums up to 57 guesses, very near to the 62 of the other method. It was easier to find the guessing candidates in these sub-puzzles, but it seemed to be longer to get to the contradictions.
So i guess, that it depends on the puzzle, which method would be faster manually.
You choose a line with say at least 5 unsolved cells, which does not allow too much permutations. Then go through them one by one.
I always wanted to know, if it's better or worse than the 2-way-guesses.
So i started to do the next tedious session, and tried Nugget with this method, again using locked candidates and subsets (the newspaper techniques).
I choose column 5 and got 35 possibilities, 18 remained after applying the techniques (the others all leaded directly to a contradiction).
For only 2 of the 18 i made more than one guess then, for one 4, the other 2 (skyscraper would save at least 2 guesses).
This sums up to 57 guesses, very near to the 62 of the other method. It was easier to find the guessing candidates in these sub-puzzles, but it seemed to be longer to get to the contradictions.
So i guess, that it depends on the puzzle, which method would be faster manually.
- eleven
- Posts: 3097
- Joined: 10 February 2008
Re: Puzzles Usage in a Presentation of a New Rating of Puzzl
by blue » Sun Mar 01, 2015 9:49 pm
eleven wrote:I also tried to avoid to make a guess for digits, which only produce one more in an empty x-wing or 2 in a 6-cell pattern, but nothing else.
Pairs don't seem to be that bad, if they only share one house (not both a box and a line).
I wondered about that too ... if it was the pairs in two houses that were the "bad eggs".
- blue
- Posts: 979
- Joined: 11 March 2013
Re: Puzzles Usage in a Presentation of a New Rating of Puzzl
by blue » Sun Mar 01, 2015 9:58 pm
Here are the rating results with standard deviations ("sigma") and min/max counts (m,M) calculated.
The table got rather wide, so I left out the data for "singles + locked candiates + subsets + basic fish".
[ This is for the method where a cell with the minimum candidate count is selected ]
The table got rather wide, so I left out the data for "singles + locked candiates + subsets + basic fish".
[ This is for the method where a cell with the minimum candidate count is selected ]
- Code: Select all
singles | +locked candiadtes | +subsets |
----------------------------+-----------------------------+-----------------------------| puzzle
rating sigma m M | rating sigma m M | rating sigma m M |
----------------------------+-----------------------------+-----------------------------+------------------------------
858.9493 661.6812 4 27368 | 621.9575 489.8724 3 21756 | 678.4785 545.3484 3 19531 | Suexrat9-10364
338.0826 253.8447 4 9493 | 261.9336 187.5185 4 7586 | 174.8692 116.2923 4 5485 | Fata_Morgana
106.9735 68.5786 4 3121 | 97.9841 64.4078 4 2949 | 68.5982 51.2504 3 2257 | Easter Monster
----------------------------+-----------------------------+-----------------------------+------------------------------
150.7094 88.3056 3 4953 | 123.7298 72.1465 3 4304 | 82.3268 51.6805 3 3372 | GoldenNugget
147.6405 87.8914 4 4194 | 123.2902 73.8630 3 3622 | 85.7411 54.3091 3 2880 | Kolk
145.6346 95.5219 4 3858 | 125.0115 83.2940 3 3506 | 85.0152 56.3454 3 2332 | Patience
139.1479 67.2834 6 2732 | 108.1807 50.4810 6 2540 | 77.7374 37.7302 4 1866 | Imam_bayildi
145.5524 112.2012 5 3201 | 117.0809 91.3956 5 2605 | 79.7549 61.5514 4 2100 | Second_flush
124.8864 74.9127 3 3678 | 105.3040 63.9248 3 3236 | 80.4641 50.0434 3 2629 | champagne_dry
119.9944 69.3432 4 3852 | 100.2021 57.5400 4 3438 | 74.2189 43.8381 3 2736 | eleven212
169.4545 89.3858 5 2666 | 140.5230 72.9459 5 2350 | 90.8898 46.1987 5 1550 | Discrepancy
128.6754 80.9999 4 3129 | 109.7834 68.3839 4 2979 | 81.5317 52.7633 4 2279 | Red_Dwarf
143.1666 80.6992 5 2600 | 82.7591 46.5790 5 1520 | 45.6534 24.9822 5 750 | AI_WorldHardest:Everest(2012)
51.6346 27.2382 3 604 | 44.3559 23.6901 3 558 | 37.7688 20.7097 3 492 | AI_WorldHardest2006Escargot
30.8243 15.4611 4 310 | 28.7598 14.0280 4 268 | 24.7899 11.2542 3 238 | AI_WorldHardest2010
65.1211 38.5058 6 1260 | 29.0808 23.6292 2 1780 | 14.7689 12.4974 2 428 | 17Hints35410
76.9150 57.2583 5 2374 | 48.0631 46.4432 2 3264 | 15.5645 14.4800 2 716 | 17Hints35409
67.5199 47.5973 1 1644 | 36.8486 26.3998 1 1035 | 43.8726 30.5088 2 2600 | 17Hints2919
18.1570 11.4057 3 112 | 15.1152 8.8262 3 76 | 15.0943 8.8332 3 76 | 17Hints41826
25.7975 15.2712 5 1088 | 12.9399 7.6489 2 268 | 15.1081 10.7991 2 508 | 17Hints48126
64.6332 35.8974 4 1692 | 52.6721 32.4805 4 1244 | 34.4980 21.7344 4 740 | JapaneseSuperComputer322
85.6295 55.9348 3 2769 | 42.8059 33.9797 2 1114 | 5.5976 3.0191 2 80 | 17Hints35043
19.1333 10.0587 3 138 | 9.0256 6.1435 2 56 | 9.0112 6.1614 2 50 | 17Hints41164
69.6821 54.4688 4 1905 | 43.1810 34.5978 2 1202 | 4.4054 1.3747 2 10 | 17Hints35045
32.7034 20.9270 3 650 | 17.1254 13.7672 2 636 | 6.3354 5.7807 2 112 | 17Hints24147
35.3365 23.9511 3 852 | 17.8776 14.6783 2 620 | 6.6121 6.6018 2 154 | 17Hints35044
32.8204 24.0518 4 524 | 19.2850 14.8968 2 618 | 3.7818 1.6706 2 36 | 17Hints35042
11.2696 7.1177 2 74 | 7.9510 5.7327 1 50 | 8.2605 5.9768 1 50 | 17Hints28653
26.7631 12.9996 4 300 | 17.5557 11.7127 2 466 | 9.2713 7.2917 2 150 | 17Hints24153
7.2228 4.8668 1 62 | 5.5842 3.5982 1 18 | 5.5918 3.6060 1 18 | 17Hints18573
8.9374 4.4667 2 34 | 5.7402 3.7673 2 26 | 5.3602 3.4945 1 32 | 17Hints42464
12.4693 7.9362 2 166 | 7.0411 6.7048 1 122 | 7.3569 7.4774 1 136 | 17Hints41972
15.5855 9.0204 3 316 | 14.2533 7.0112 3 210 | 5.0847 3.5962 1 58 | 17Hints32733
17.3935 10.9517 2 158 | 7.4061 8.5293 1 128 | 9.7625 10.4903 1 142 | 17Hints33052
20.5692 14.2836 2 206 | 7.9810 9.6946 1 158 | 10.8056 12.0252 1 172 | 17Hints4934
13.9067 8.1658 2 310 | 12.9607 7.2982 2 234 | 9.3619 4.8879 2 200 | JapaneseSuperComputer313
35.1865 25.5756 3 722 | 21.1222 15.5642 2 442 | 3.1004 2.4703 1 48 | 17Hints41750
5.4854 2.8811 2 16 | 5.3650 2.9366 1 18 | 5.3650 2.9366 1 18 | 17Hints12538
8.8403 4.5058 2 26 | 4.4944 2.3236 1 12 | 4.4944 2.3236 1 12 | 17Hints12995
7.1596 3.6622 2 92 | 5.4240 2.6639 2 42 | 5.3995 2.9021 1 44 | 17Hints21752
6.9403 4.2317 2 38 | 6.7366 3.8998 2 34 | 6.7533 3.8503 2 34 | 17Hints26041
8.1493 3.8598 2 40 | 6.5542 3.8178 1 32 | 5.5294 3.5086 1 32 | 17Hints39923
17.7356 12.0188 3 202 | 4.0557 1.6322 2 8 | 4.0557 1.6322 2 8 | 17Hints40086
88.9682 95.2481 2 9832 | 28.3550 31.7482 1 3626 | 1.5000 0.5000 1 2 | 17Hints44580
6.2596 2.9969 2 22 | 5.1312 2.6582 2 22 | 4.9402 2.6775 2 22 | 17Hints47137
6.3676 3.1005 2 20 | 4.6196 3.5348 1 20 | 4.9621 3.7229 1 20 | 17Hints48498
3.9583 2.4953 1 18 | 3.9658 2.5029 1 18 | 3.9725 2.5098 1 18 | 17Hints8780
3.1147 1.9455 1 10 | 3.0647 1.9504 1 10 | 3.0647 1.9504 1 10 | 17Hints9404
- blue
- Posts: 979
- Joined: 11 March 2013
Re: Puzzles Usage in a Presentation of a New Rating of Puzzl
by tknottet » Mon Mar 02, 2015 11:17 am
denis_berthier
I found that a cause(at least one of causes) that the rating value of Imam Bayildi(minimal version) is smaller than that of its isomorph(non-minimal version) is because my rule15 is not confluent.
I found a situation in solving path of the isomorph where the rule15 should be applied but is not applied.
It causes to raise the isomorph's rating value.
The cause that the rule15 is not applied in case of the isomorph is because my rule8 which is used to create "Off Off Vectors" is not confluent.
Which digits are eliminated by rule8 is influenced by number permutation.
The difference is not fatal in usual solving, but it is fatal in application of the rule15.
For many rules in my T including rule8, when the rule is applied once, the processing is over there. It causes non-confluence. It takes time for the solution to this problem. For a while, I must add some apologize on my hardest sudoku list page.
Thank you very much again for explaining non-confluence phenomenon many times.
I found that a cause(at least one of causes) that the rating value of Imam Bayildi(minimal version) is smaller than that of its isomorph(non-minimal version) is because my rule15 is not confluent.
I found a situation in solving path of the isomorph where the rule15 should be applied but is not applied.
It causes to raise the isomorph's rating value.
The cause that the rule15 is not applied in case of the isomorph is because my rule8 which is used to create "Off Off Vectors" is not confluent.
tknottet wrote:( at Thu Feb 26, 2015 11:50 pm )
(1-2)After Ca is eliminated, r7(Locked Candidates), r8(Naked Pair/Triple/Quad) and r9(Hidden Pair/Triple/Quad) is applied separately. If Cb is eliminated by any of(not 'oh') these application, "Off Off Vectors" is defined from Ca to Cb.
Which digits are eliminated by rule8 is influenced by number permutation.
The difference is not fatal in usual solving, but it is fatal in application of the rule15.
Hidden Text: Show
For many rules in my T including rule8, when the rule is applied once, the processing is over there. It causes non-confluence. It takes time for the solution to this problem. For a while, I must add some apologize on my hardest sudoku list page.
Thank you very much again for explaining non-confluence phenomenon many times.
- tknottet
- Posts: 24
- Joined: 15 February 2015
Re: Puzzles Usage in a Presentation of a New Rating of Puzzl
by denis_berthier » Mon Mar 02, 2015 12:57 pm
Hi tknottet
Some points remain to be improved but your rating is interesting and raises interesting questions.
Ratings that do not give the same value to isomorphic puzzles are not so rare. It's not dramatic per se (if it doesn't happen too often). SER is well known for having the problem occasionally. Whips and the W rating have the same problem (very rarely in practice), only braids and the B rating are free of it; but whips are so much simpler that the W rating remains my preferred one.
Non confluence can be more of a problem for the programmer if he spends a long time trying to find a bug in the code (he can't find anything in the code).
Some points remain to be improved but your rating is interesting and raises interesting questions.
Ratings that do not give the same value to isomorphic puzzles are not so rare. It's not dramatic per se (if it doesn't happen too often). SER is well known for having the problem occasionally. Whips and the W rating have the same problem (very rarely in practice), only braids and the B rating are free of it; but whips are so much simpler that the W rating remains my preferred one.
Non confluence can be more of a problem for the programmer if he spends a long time trying to find a bug in the code (he can't find anything in the code).
- denis_berthier
- 2010 Supporter
- Posts: 3972
- Joined: 19 June 2007
- Location: Paris
Re: Puzzles Usage in a Presentation of a New Rating of Puzzl
by denis_berthier » Mon Mar 02, 2015 1:02 pm
Hi blue,
Very interesting and surprising (so large max) results.
I wonder what's the max value when all the candidates are tried.
On my side, I'm running calculations with my T&E procedure to compare the two strategies (random vs bivalue/bilocal preferred)
Very interesting and surprising (so large max) results.
I wonder what's the max value when all the candidates are tried.
On my side, I'm running calculations with my T&E procedure to compare the two strategies (random vs bivalue/bilocal preferred)
- denis_berthier
- 2010 Supporter
- Posts: 3972
- Joined: 19 June 2007
- Location: Paris
Re: Puzzles Usage in a Presentation of a New Rating of Puzzl
by eleven » Mon Mar 02, 2015 8:41 pm
When i looked at blue's table, i felt a bit better, because i realized, that the 62 guesses in my Nugget experiment are the worst case. The best case for my selected guessing candidates is 5, and the average 32.5, if i calculated that correctly.
I tried to find out, how 10 guesses could be needed for the last puzzle, but i cannot reach that, if, when a candidate lead to a contradiction, i immediately try the other candidate of the cell. Is that right ?
I tried to find out, how 10 guesses could be needed for the last puzzle, but i cannot reach that, if, when a candidate lead to a contradiction, i immediately try the other candidate of the cell. Is that right ?
- eleven
- Posts: 3097
- Joined: 10 February 2008
Re: Puzzles Usage in a Presentation of a New Rating of Puzzl
by blue » Mon Mar 02, 2015 9:03 pm
I've finished trying all sorts of things with bi-local candates, and bi-value/bi-local mixes, and different kinds of filtering.
Everything was run with a "T" that included singles, locked candidates and subsets.
In absolutely every case that involved bi-local candidates, the ratings were worse than with bi-value cells only.
That included even the cases where a bi-local candidate is used only when there are no bi-value cells to choose from.
[ For a couple of the combinations, there were a (quite) small number puzzles in the list, where the rating improved, but the overall effect was never good. ]
The actual ratings, are probably not worth posting.
When I first tried "bi-locals only" (and no bi-value cells), there were so many options to choose from, that the code ran out of RAM before finishing the calculation -- RAM used to store ratings and "good/bad" flags for the intermediate puzzle states. I tried a Monte Carlo rating, at that point, for "Golden Nugget" only ... and it was a little over 2x what it was with "cells only". At that point, I added a filter for the bi-local candiadtes, that rejected cases where the candidates were in the same box and same row or column. That reduced the problem enough so that the code didn't run out of RAM, but the rating for "Golden Nugget" was still aroung 1.5 times what it was with "cells only". After that, though, everything that I tried with bi-locals, included that filter, at least.
The one thing that I did have luck with, was a filter for the "cells only" approach, that ignored cells that were part of a locked set confined to both a box and a line. That lowered most (?) of the ratings by a little bit (Gold nugget went from 82 to 75), and it also cured the problem where for a few puzzles, the rating went up when subsets were added.
==
Yes, I was surprised by that too -- larger than the average by many multiples of the standard deviation !
==
This is more or less exactly the opposite of what I was seeing.
Either your filtering method is very good (likeliest ?), or we aren't calculating the same thing.
Yes, and you need to count the other candidate as a "guess" ... more or less because you need to apply "T" at that point, and run it to a point where either another guess is required, or the puzzle is solved or showing a contradiction.
P.S.: Here's a sequence of 10, for that last puzzle:
Everything was run with a "T" that included singles, locked candidates and subsets.
In absolutely every case that involved bi-local candidates, the ratings were worse than with bi-value cells only.
That included even the cases where a bi-local candidate is used only when there are no bi-value cells to choose from.
[ For a couple of the combinations, there were a (quite) small number puzzles in the list, where the rating improved, but the overall effect was never good. ]
The actual ratings, are probably not worth posting.
When I first tried "bi-locals only" (and no bi-value cells), there were so many options to choose from, that the code ran out of RAM before finishing the calculation -- RAM used to store ratings and "good/bad" flags for the intermediate puzzle states. I tried a Monte Carlo rating, at that point, for "Golden Nugget" only ... and it was a little over 2x what it was with "cells only". At that point, I added a filter for the bi-local candiadtes, that rejected cases where the candidates were in the same box and same row or column. That reduced the problem enough so that the code didn't run out of RAM, but the rating for "Golden Nugget" was still aroung 1.5 times what it was with "cells only". After that, though, everything that I tried with bi-locals, included that filter, at least.
The one thing that I did have luck with, was a filter for the "cells only" approach, that ignored cells that were part of a locked set confined to both a box and a line. That lowered most (?) of the ratings by a little bit (Gold nugget went from 82 to 75), and it also cured the problem where for a few puzzles, the rating went up when subsets were added.
==
denis_berthier wrote:Very interesting and surprising (so large max) results.
Yes, I was surprised by that too -- larger than the average by many multiples of the standard deviation !
==
eleven wrote:When i looked at blue's table, i felt a bit better, because i realized, that the 62 guesses in my Nugget experiment are the worst case. The best case for my selected guessing candidates is 5, and the average 32.5, if i calculated that correctly.
This is more or less exactly the opposite of what I was seeing.
Either your filtering method is very good (likeliest ?), or we aren't calculating the same thing.
eleven wrote:I tried to find out, how 10 guesses could be needed for the last puzzle, but i cannot reach that, if, when a candidate lead to a contradiction, i immediately try the other candidate of the cell. Is that right ?
Yes, and you need to count the other candidate as a "guess" ... more or less because you need to apply "T" at that point, and run it to a point where either another guess is required, or the puzzle is solved or showing a contradiction.
P.S.: Here's a sequence of 10, for that last puzzle:
- Code: Select all
7r9c5 -> bad
8r6c1 -> bad
2r9c9 -> bad
9r8c4 bad
5r8c4 -> bad
7r1c8 bad
9r1c8 bad
9r9c9 bad
9r6c1 bad
9r9c5 good
Last edited by blue on Mon Mar 02, 2015 11:27 pm, edited 1 time in total.
- blue
- Posts: 979
- Joined: 11 March 2013
Re: Puzzles Usage in a Presentation of a New Rating of Puzzl
by eleven » Mon Mar 02, 2015 10:57 pm
Many thanks, blue, for calculating that.
It's not the first time that a sudoku conjecture of me is totally wrong
I checked my Nugget notes, and found that i had left a possibility open, which added 7 guesses. So the sum is 69, and the average 37.
Note that i both had used bilocal and bivalue guesses.
Concerning the last puzzle i had totally overlooked the bad choices.
Another question i am very interested in, is how the T&E ratings of puzzles with the same ER in the range 7/8 would differ. Would it be possible e.g. to rate say 100 random puzzles each with ER 7.3 and 8.3 ?
It's not the first time that a sudoku conjecture of me is totally wrong
I checked my Nugget notes, and found that i had left a possibility open, which added 7 guesses. So the sum is 69, and the average 37.
Note that i both had used bilocal and bivalue guesses.
Concerning the last puzzle i had totally overlooked the bad choices.
Another question i am very interested in, is how the T&E ratings of puzzles with the same ER in the range 7/8 would differ. Would it be possible e.g. to rate say 100 random puzzles each with ER 7.3 and 8.3 ?
- eleven
- Posts: 3097
- Joined: 10 February 2008
Re: Puzzles Usage in a Presentation of a New Rating of Puzzl
by blue » Tue Mar 03, 2015 2:31 am
eleven wrote:Another question i am very interested in, is how the T&E ratings of puzzles with the same ER in the range 7/8 would differ. Would it be possible e.g. to rate say 100 random puzzles each with ER 7.3 and 8.3 ?
These were the first 100 that I got with ER in that range.
I didn't get a good spread of values ... most are 7.3 or 8.3.
Also most all (if not all of them) have singles in the beginning.
I tried producing some with an ED in that range too, but with no luck (... it would have taken a long long time).
If you have another list that you'ld like me to rate, I'ld be happy to do it.
The 3 "tknottet" ratings are for singles, singles & locked candiates, and singles, locked candiates & subsets.
Hidden Text: Show
Best Regards,
Blue.
- blue
- Posts: 979
- Joined: 11 March 2013
Re: Puzzles Usage in a Presentation of a New Rating of Puzzl
by denis_berthier » Tue Mar 03, 2015 5:05 am
Computational disadvantage of preferring bivalue/bilocal cells in T&E
In this post, I'm not speaking of exactly the same thing as tknottet, eleven or Blue's DFS procedure.
Below, T&E always means the procedure I have defined as T&E (which I’ve always considered as the mere formalisation of what players usually mean by T&E and also of Ruud's original definition in Sudopedia - now disappeared):
- it has no guessing (if a tried candidate leads to a solution, the corresponding path is merely forgotten);
- it tries all the candidates at some depth before going deeper;
- it may try candidates at some depth several times so that the result at this depth is independent of the order they are tried (a necessary condition for the procedure being well defined).
I’ve shown years ago that all the known puzzles can be solved at depth 2 (at most) and Blue has shown that only 1 puzzle in about 30,000,000 requires more than depth 1.
What I compare below is two different strategies for trying all the candidates at some depth: (pseudo) random and bivalue/bilocal first.
Notice that the T&E strategy used has no impact on the resolution state reached at each depth; it can only change the computation times.
As I said above, T&E is very different from ttknottet’s DFS procedure. However, I think the comparisons below about the preference for bivalue/bilocal cells, valid for my T&E definition, should me more or less valid for DFS.
The results below must be taken with some grain of salt:
- they are implementation-dependent (they were obtained with the latest version of SudoRules, based on my general pattern-based CSP-Rules solver)
- they rely on small samples
- my T&E procedure is generic (it works for any CSP) but it is very far from being optimised for Sudoku
- all the timings are relative to the first cell of each table, arbitrarily set to 1
- in the first two samples, many puzzles can be solved without T&E
- the cb collection (controlled-bias) is the closest we can get to a random unbiased one (I didn’t consider worth doing the corrections for the known bias); all the puzzles are in T&E(1)
- the magictour-top234 collection was once considered as the hardest, but that was long ago; it remains among the hardest puzzles solvable by human brains; no puzzle in it can be solved without T&E (i.e. with only the rules in BRT or W1) but almost all are in T&E(1) and all are in gT&E(1)
- the eleven’s-hardest collection is version V2_26370.tx of eleven’s collection of puzzles not in T&E(1, S4) i.e. not solvable by S4-braids; I consider only the first 100, i.e. the hardest; no puzzle is in T&E(1)
For each collection, I used only T&E(T, 1), i.e. no T&E level deeper than 1. It implies that a few puzzles may be only partly solved, but it doesn’t matter for the comparison, as the 2 strategies lead to the same final resolution states (T fixed).
The only exception is eleven’s collection, for which I also tried T&E(T, 2). In this case, all the puzzles are solved.
Notations:
BRT = universal Basic Resolution Theory (= Singles + ECP)
W1 = BRT + whips[1] (= claiming and pointing)
bivalue-first: try first any candidate in a bivalue/bilocal cell
The format for each cell is: mean time - max time (each value is relative to first cell)
- Code: Select all
Rules in T BRT BRT
T&E strategy random bivalue-first
Royle17-1-100 1 - 1 0.96 - 0.91
cb-1-100 1.06 - 1.68 1.02 - 1.64
magictour-top234 6.26 - 13 6.61 - 15
eleven’s-hardest-0-100 (1) 9.07 - 7.18 9.20 - 7.27
eleven’s-hardest-0-100 (2) 73.2 - 144.9 76.7 - 146.3
Comment: there is no significant difference between the two strategies for T&E
Now we add whips[1] to T. The final states are still the same for the 2 strategies, but possibly different from above (closer to solution)
- Code: Select all
Rules in T W1 W1
T&E strategy random bivalue-first
Royle17-1-100 1 - 1 0.95 - 0.6
cb-1-100 1.11 - 1.33 1.07 - 0.94
magictour-top234 10.8 - 19.2 6.26 - 8.9
eleven’s-hardest-0-100 (1) 55 - 34.3 8.4 - 4.2
eleven’s-hardest-0-100 (2) 185.8 - 319.4 591 - 708
Comments:
I was surprised by the results for gT&E = T&E(W1). Preference for the bivalue/bilocal candidates seems to give faster calculations at depth 1 for the hard puzzles (no full solution found at this depth), but slower at depth 2. (I checked the results 3 times.)
For puzzles that can be solved by T&E (almost all the puzzles), using gT&E instead leads to a slower procedure.
For puzzles needing T&E(2), the bivalue strategy is much slower for gT&E(2). It is faster for gT&E(1) (producing only partial results).
Globally, I conclude that the bivalue/bilocal strategy is rarely good, confirming the impression I had when I watched hundreds of resolution paths for hard puzzles: long streaks of whips with no Single in between (in SudoRules, an elimination for a bivalue would be immediately followed by a Single).
I didn't try using only bivalue candidates instead of bivalue/bilocal.
- denis_berthier
- 2010 Supporter
- Posts: 3972
- Joined: 19 June 2007
- Location: Paris
Re: Puzzles Usage in a Presentation of a New Rating of Puzzl
by dobrichev » Tue Mar 03, 2015 9:23 am
blue wrote:...If you have another list that you'ld like me to rate, I'ld be happy to do it.
Hi Blue,
Are there rating anomalies in these puzzles?
- Code: Select all
... ... ..1
... ..2 .3.
..4 .5. 6..
... .6. 57.
..5 ..8 4.6
.9. .47 .8.
..3 1.. ...
51. ... ...
64. .3. ... 9.6/1.2/1.2
- Code: Select all
000400700050100000080030100000360090091000840000000000700090060004020000005800030 22 4 7.1/2.3/2.3
000400700050000000080030100000360090091000840000008000700590460030620000065800030 26 4 7.1/1.2/1.2
12.4..7...5.1......8..3.1.....36..9..91...84....9.8...71.59346..3462.....658...3. # 98896 FNBTHG C33/M4.2047.259
- dobrichev
- 2016 Supporter
- Posts: 1850
- Joined: 24 May 2010
Re: Puzzles Usage in a Presentation of a New Rating of Puzzl
by blue » Tue Mar 03, 2015 10:34 am
dobrichev wrote:Are there rating anomalies in these puzzles?
Hi Mladen,
In the first one, yes, but it's removable with the "no cells in locked sets in a mini-line" filter.
The last one shows something new -- a higher rating with locked candidates than with singles only !
- Code: Select all
singles | +locked |+subsets | subsets
| cands. | | +filter
--------+---------+---------+--------
95.7187 | 80.7856 | 93.1054 | 78.3496 min = 5,5,5,5
20.3089 | 18.5035 | 13.5272 | 12.3411 min = 4,4,4,4
9.7053 | 8.5848 | 8.1214 | 7.8492 min = 4,4,4,4
6.7648 | 6.9055 | 6.8470 | 6.6156 min = 4,4,4,4
--------------
P.S: I hadn't though to apply the filter to cases where the solver wasn't using subsets, since the solver wouldn't be turning hidden pairs (& triples) into naked pairs (& triples) just before each guess.
I've done that now, and the results are below.
The numbers in brackets are with the filter applied.
The last one seems OK now, but the first one shows an anomoly again !
Interesting.
- Code: Select all
singles | +locked cands. | +subsets
-----------------+------------------+-----------------
95.7187[80.0832] | 80.7856[66.5267] | 93.1054[78.3496]
20.3089[18.5035] | 18.5035[17.1625] | 13.5272[12.3411]
9.7053[ 8.5848] | 8.5848[ 8.2976] | 8.1214[ 7.8492]
6.7648[ 6.9055] | 6.9055[ 6.6464] | 6.8470[ 6.6156]
- blue
- Posts: 979
- Joined: 11 March 2013
