The New Sudoku Players' Forum

[tarek]

... the three puzzles with gsfr below 99800 - do they actually need coloring in contradiction chains? If not, any explanation then why they are not solved by Explainer, and why they cannot be RMS-rated? The gsfr for these varies significally: #114 (gsfr=99687), #116 (gsfr=99527), #106 (gsfr=99325).

My program is stuck after 15, 4 and 8 eliminations for these 3 puzzles, though it tries all remaining candidates.

Could it be that gsf's solver does eliminations in BATCHES & yours doesn't....If that is the case then a simple improvement would be to keep MEMORY of all past POSSIBLE eliminations as you go forward (to use them when stuck or even to shorten the solution, which is what you're doing)

As you well know some eliminations under a certain set of techniques may DISAPPEAR off the radar if an earlier elimination done was vital for those eliminations.

tarek

[ravel]

Could it be that gsf's solver does eliminations in BATCHES & yours doesn't....

No, in these cases, when my program is finally stuck with a grid, it has made all eliminations it can do.
In the moment i have absolutely no time to search for bugs. But it would be a great help later, when someone could tell me, which elimination my prog missed. This is, where it is stuck with Ocean's nr 3/gold list:

Code: Select all

4679  6789   1     | 3589     35789  2      | 346   689    3489       
2679  3      268   | 189      4      78     | 126   5      189       
5     489    248   | 6        389    189    | 7     1289   13489     
----------------------------------------------------------------
2349  459    7     | 1234589  3589   14589  | 1245  128    6         
2469  1      2456  | 24589    56789  456789 | 245   3      4578       
8     456    23456 | 12345    3567   1456   | 9     127    1457       
----------------------------------------------------------------
1467  45678  9     | 458      568    3      | 156   167    2         
367   2      3568  | 589      1      5689   | 356   4      3579       
1346  456    3456  | 7        2      4569   | 8     169    1359       


[gsf]

Could it be that gsf's solver does eliminations in BATCHES & yours doesn't....If that is the case then a simple improvement would be to keep MEMORY of all past POSSIBLE eliminations as you go forward (to use them when stuck or even to shorten the solution, which is what you're doing)

As you well know some eliminations under a certain set of techniques may DISAPPEAR off the radar if an earlier elimination done was vital for those eliminations.

good point
you can test by adding the -S (step) option that commits to the first
candidate elimination for any constraint, including propositions

what candidate elimination is hit first for each constraint is algorithm-specific,
but is usually biased towards cells with the least number of candidates
(that's the reason for batching -- to wash the algorithm-specific bias)

-S on the three puzzles reaches solutions using the same proposition constraints (but typically more steps),
so stepwise solution paths do exist for these puzzles

[gsf]

This is, where it is stuck with Ocean's nr 3/gold list:

Code: Select all

4679  6789   1     | 3589     35789  2      | 346   689    3489       
2679  3      268   | 189      4      78     | 126   5      189       
5     489    248   | 6        389    189    | 7     1289   13489     
----------------------------------------------------------------
2349  459    7     | 1234589  3589   14589  | 1245  128    6         
2469  1      2456  | 24589    56789  456789 | 245   3      4578       
8     456    23456 | 12345    3567   1456   | 9     127    1457       
----------------------------------------------------------------
1467  45678  9     | 458      568    3      | 156   167    2         
367   2      3568  | 589      1      5689   | 356   4      3579       
1346  456    3456  | 7        2      4569   | 8     169    1359       


if r1c2=6 is proposed at this position then the puzzle solves with singles and box-line
this is the only singles/box-line solution/elimination for a cell with <= 3 candidates at this position
(my solver proposition logic scans cells with the least number of candidates first,
and with batching stops the iteration at cell count n when at least
one elimination/solution is found for all cells with <= n candidates)

[ravel]

if r1c2=6 is proposed at this position then the puzzle solves with singles and box-line

Hm, my program found this backdoor, but it ignores backdoors, because they dont lead to an acceptable solution, but just to a solution with a lucky guess. If i would use them, all single backdoor cell puzzles would require just one step.

[gsf]

if r1c2=6 is proposed at this position then the puzzle solves with singles and box-line

Hm, my program found this backdoor, but it ignores backdoors, because they dont lead to an acceptable solution, but just to a solution with a lucky guess. If i would use them, all single backdoor cell puzzles would require just one step.

agreed that "here's a backdoor" is not an acceptable solution
that's where batching enters the picture
if you take into account every candidate for each puzzle position then
the backdoors become a statistic that factors into puzzle difficulty

the proposition constraint is pure mechanical guessing
when batched it applies the proposition constraints on all candidate values for the current position
if a solution is hit its not ignored because of luck
with batching there is no luck since all candidates are attempted
and all solutions at a position are collected
but once solution(s) are found during a proposition iteration the solver stops at the end of the iteration
what human wouldn't stop once a solution were found?

batching gets a handle on how much luck a random guesser would require to hit a solution
the hardest puzzles require stronger proposition constraints and more batched proposition iterations to reach a solution

this particular puzzle yields no contradiction/solution for singles proposition constraints
but yields 1 solution in one iteration for singles/box-line constraints

so its somehow tougher than a puzzle that yields 10 solutions in one iteration for singles/box-line constraints
but not as tough as one that requires more proposition iterations or stronger proposition constraints

the current hardest puzzles require multiple proposition iterations using
multi-coloring in the proposition constraints

[ravel]

I can follow your reasoning (and personally also would stop, when i find a solution after "testing" a candidate in an ultrahard puzzle).
But as i said before, my ideal of rating the hardness of a puzzle is to rate the shortest possible solution (whatever this is and however it can be found, but it must not contain a "guessing step").
So we have 2 different philosphies and our ratings are based on different properties of a puzzle.

[ravel]

These are the ratings RMS(gsfr) for 8 puzzles, which i must not publish here without a written permission:
N/A (99415), 18 (99718), 11 (99585), N/A (99838X), N/A (99496), 14 (99428), 16 (99534), 9 (99557)

Not bad for a commercial product
I inserted the 3 hardest into the top list as "commercial".

[RW]

agreed that "here's a backdoor" is not an acceptable solution
that's where batching enters the picture
if you take into account every candidate for each puzzle position then
the backdoors become a statistic that factors into puzzle difficulty

Is there a way to tell your program not to use backdoor solutions but only eliminations to reach the solution? It would be interesting to know what proposition constraints are required to reach the solution by elimination in the puzzles your solver solves with backdoors.

RW

[m_b_metcalf]

After all we know now, just searching puzzles with those patterns could be a good method to create puzzles for the hardest list, though the 2 ones are much too easy

Right, but there is something I really don't understand. Consider three different ways to generate a valid puzzle with a given pattern:

1) Generate a grid, minimalize it (or nearly), check whether it happens to correspond to the desired pattern.

2) Generate a grid, select from it those cells corresponding to the pattern, check whether this candidate puzzle has a unique solution.

3) Clear a grid, add the candidate clues 1 - 9 to each cell corresponding to the pattern, iterate over a subset of the possibilities, checking whether each candidate puzzle has a unique solution (it may, of course, have no solution).

Clearly 1) is almost a lost cause. I have two independent programs that use method 2) and one that uses method 3). This last program has a far higher yield than the other two (which are comparable in performance). This I cannot understand. Does anyone know why this should be? (In theory, a candidate puzzle in 2) will, in general, correspond to multiple full grids, and hence can be selected multiple times, leading to redundancy. In practice, the numbers are so huge that this effect cannot be measured. I know, I tried.)

Thanks for any enlightenment. And are there better ways still than 3)?

Mike Metcalf

P.S. Is there any way of running SE on a file of puzzles in some standard format (on Windows XP)?

[RW]

These are the ratings RMS(gsfr) for 8 puzzles, which i must not publish here without a written permission:
N/A (99415), 18 (99718), 11 (99585), N/A (99838X), N/A (99496), 14 (99428), 16 (99534), 9 (99557)

The SE ratings:
N/A , 9,5 , 10,0 , N/A , 9,4 , 9,9 , 9,8 , 9,5

Most interesting is the fifth. Your solver couldn't solve it, but SE gave 9,4... you can probably check yourself with Explainer how this is possible. I couldn't see anything in SE's solution that should be too hard for your program.

All of the puzzles are diagonal, except the last one that differs from the diagonal pattern in 4 boxes. Probably one of the toughest non-diagonal puzzles around.

P.S. Is there any way of running SE on a file of puzzles in some standard format (on Windows XP)?

I'm afraid not. All puzzles must be entered/pasted individually.

RW

[tarek]

These are the ratings RMS(gsfr) for 8 puzzles, which i must not publish here without a written permission

Anyone digging long enough, let's say 3 months with billions of diagonal pattern puzzles will hit something

P.S. Is there any way of running SE on a file of puzzles in some standard format (on Windows XP)?

I'm afraid not. All puzzles must be entered/pasted individually.

I am painfully & very slowly doing that on Hardest hopefuls which I generated last week (10-15/day) .... nothing sparkling (2 weeks ago it would have been sparkling), will post some tomorrow.....

tarek

[gsf]

agreed that "here's a backdoor" is not an acceptable solution
that's where batching enters the picture
if you take into account every candidate for each puzzle position then
the backdoors become a statistic that factors into puzzle difficulty

Is there a way to tell your program not to use backdoor solutions but only eliminations to reach the solution? It would be interesting to know what proposition constraints are required to reach the solution by elimination in the puzzles your solver solves with backdoors.

not now
I'll add it to next week's post
a quick check shows it forcing most of the hardest to multi-coloring in the proposition constraints

but I still don't get this aversion to backdoors found during an exhaustive search
since its exhaustive (well, exhaustive over all cells with n candidates) backdoors are inevitable
the same machinery that finds contradictions also finds solutions
in batched mode the solver doesn't stop at the first backdoor, but instead continues to
find all eliminations/backdoors for all cells with n candidates
and this is factored into the stats for the puzzle
there's no luck involved, although the stats could be used to estimate how
lucky a human solver would have to be to solve the puzzle

I guess its just the fundamental difference between solving to rate vs solving to find aesthetic solution paths

[RW]

but I still don't get this aversion to backdoors found during an exhaustive search
since its exhaustive (well, exhaustive over all cells with n candidates) backdoors are inevitable
the same machinery that finds contradictions also finds solutions
in batched mode the solver doesn't stop at the first backdoor, but instead continues to
find all eliminations/backdoors for all cells with n candidates
and this is factored into the stats for the puzzle

I agree that the backoors should be factored into the stats for the puzzle. However, I think the full path to the solutions using eliminations should also be factored into the solution. As it is now, your program might apparently rate puzzles without including all required eliminations in the "aestethic solving path", like in this case with ocean's #3. I think this is the problem at the moment.

RW

[ravel]

Most interesting is the fifth. Your solver couldn't solve it, but SE gave 9,4... you can probably check yourself with Explainer how this is possible. I couldn't see anything in SE's solution that should be too hard for your program.

Thank you, RW, i reran this puzzle now and soon got solutions with 14 and 13 steps. I have to check where the mistake was (copy, parameters, misreading the trace ?), when i have more time.