dailysudoku.com

[someone_somewhere]

Hi,
I would be glad for ideas of how to measure the difficulty of a SuDoku position. I have something in mind, but would be glad for any suggestion.

[Max Beran]

My candidate for this role is a simple summation of all the number of possibilities in all the unsolved cells. The rationale is that it is the number that you're trying to whittle down to zero so on average the higher the number from any position then the greater the effort required to do the whittling.

I've done a reasonable amount of work and it certainly isn't perfect. Numbers over 210 are certainly taxing and below 180 tend to be a doddle.

BUT, and this is a big but, it is not necessarily successful in identifying cases with cunningly hidden triplets or xy-chains so it may even be possible to construct a puzzle that is fiendish to solve but has quite a low score.

Then there's the additional problem of an objective measure to compare it with. One might have hoped that the computer solutions would provide ideal numbers with which to calibrate any score such as the one I've been working with. But this turns out not to be so. The practised eye can spot ways of rapidly depleting the "candidate score" (which is what I've termed the above summation) but the poor old computer has to slog through with laborious applications of simple rules.

Another point worth mentioning is that there is 0.95 correlation between the candidate score and the current number of filled cells (which is of course hugely less work to compute).

I'd love to hear your idea.

[someone_somewhere]

here some other comments on this subjects (that I have exchanged) with someone else:

How about "average number of possibilities per spot" after doing a first pass of cleaning out the obvious impossibilities (where that digit is already present in the row/column/box)?

The cleaning - I call the "exclude" of a number for a cell. Meaning that it can not be there. Than the process of "excluding" has 2 phases:
1. the, let's call them direct excludes. You called them "obvious impossibilities".
2. the, let's call them indirect excludes. I have analysed this kind of excludes and think that I have found them all.
So, trying to solve a position (without a program) you will tend to use (because of the optic) only the first category, and only when you don't find a number, you will have to start thinking about the second category.
What about getting to evaluate a position with a single number, something like the entropy ?!
If you know the game mastermind, you will have to select the question that induces the minimum entropy, or in other words, gets the maximum of information, independent of the oponents response.

Ok. I think that the difficulty of a game should be measured as the sum of the difficulties of each step. One step is finding a number in a cell and than we get to the next step (except when we found the last number).
Now we reduced the problem to define the difficulty for a step, of a position. Here we will have a set of possibilities out of all that are left. This ones can be of 2 kinds. The first - simple, that can be found after we did the direct Excludes and second - complex, that can be found ONLY when doing the indirect Excludes. Now the difficulty is dependent on the number of indirect excludes we have to do.
The question is: how should I quantify the "indirect" excludes and their numbers and their dependency (meaning that a indirect exclude is a prerequirement of a second indirect exclude, etc).
When you try to get the 11 numbers that can be found with "logic" only, out of the following:

043080250
600000000
000001094
900004070
000608000
010200003
820500000
000000005
034090710

meaning trying to solve the first 11 numbers, you will understand better that I mean. This diffiulty is of course refering to humans and not computer programs.
Any feedback, ideas ?!

[Max Beran]

Not sure if your last posting was addressed to me as it mentioned "obvious impossibilities", not a term that appears in my piece.

Anyway, a few instant reactions -

1. Why average when it is the total that matters. You could at a late stage in the solution arrive at a point where the remaining cells still have a fair number of possibilities even though they rapidly melt away. It seems obvious to me that an average of 4 possibilities over 55 cells is a hugely different proposition than an average of 4 over 5 cells.

2. Why exclude obvious excludes - they are part of what makes a puzzle hard or easy? If the setter is kind enough to make the solver's life easy, it seems actually misleading to engineer a score that gives the impression that it is harder than it is.

3. Some measure of dispersion or non-intersection could be useful and I was trying to dream them up - nearest neighbour statistics in a row-col-box space. Would it operate on the the filled or unfilled cells? Is a dispersed set harder than a clustered disposition of the same number of cells? I would speculate that if the given cells are strongly interconnected (whatever that might convert to quantitatively) then the puzzle will be that much harder.

4. Is the object a measure of the difficulty of the current situation (as your initial post implied) or of the original puzzle as set? And if the latter, do you seek a measure that can be obtained by the puzzler from inspection of the cells as they stand (to check if it's worth their while attempting it), or is it a score that the setter can quote having solved the puzzle manually or by program? These all have a bearing on the approach I think. Mepham of DT says that the assignment of difficulty category is subjective.

I'll have a look at your puzzle and see if it sparks any further comment.

Max

[schwa]

I think the product, rather than the sum, might be a better measure.

Or take the log of the product, if you like.

What do you think of that idea?

--Joshua

[Guest]

[Max Beran]

Using the product (or any other transformation) seems to make little sense. By amplifying the relative contribution of small count numbers over larger ones it iturns upside down what one might think is the natural order. For example, it says that an elimination step that reduces three possibilities to two is much more important than reducing 7 to 6 even though the actual skill required to do both is the same.

A simple summation appears to me to be a natural metric reflecting the average bnefit of the average step. It would also be easier to introduce into a running total over several puzzles, eg in a competition or time trial.

[Guest]

someone-somewhere

I presume you got the puzzle out to this stage:

043]980]250
600]425]000
200]001]094
--------------
900]004]070
300]608]000
410]209]003
---------------
820]500]000
000]040]005
534]890]710

It is solvable by logic beyond this point by using the X-wing based on the '6' candidates at r1 c6 and c9, and r9 c6 and c9. This allows you to eliminate 6's at r4c0, r7c6 and r7c9 after which the cells tumble into place with no further clever stuff.

On the candidate score this was a 237-er suggsting it's well up at the difficult end of the spectrum, which is absolutely right - it was.

[someone_somewhere]

[Max Beran]

Dear Guest (the one who offered Schwa to run tests on his archive of 200 puzzles)

The offer is mighty generous. Can I take you up on it? I would love to receive a data file with the following numbers for each puzzle:

1. The Candidate Score - being the summation of the number of candidates over the entire set of unsolved cells.

2. The number of solved cells as provided by the setter

3. Data to construct a measure of the overall tightness of the solved cells - the tighter they are, the more difficult it is to solve the puzzle (at least that is my hypothesis). What follows is an attempt at this:

Using the solved cells, fist create a table showing its row number, column number and box number (the domains). Then for each solved cell cycle through each of the other solved cells and count how many cells share with it a single domain (ie in the same row or column or box), share two domains (eg a row and a box or a column and a box), and share no domains. Organise the cycling through the pairs in such a way that you don't include the same pair twice. What I would like as output is the three numbers being to total number of one-domain links, two domain links and zero domain links. I can then play tunes on these to try to derive a single number index of difficulty and compare it with the others.

4. Does your program also generate any output that these scores could be correlated with and that might objectively quanify how difficult it was for the computer to solve? The sort of thing I have in mind is the total number of program steps that are there to eliminate candidates but do not end up with a solved cell; how many naked and hidden couplet, triplet, or x-wing steps.

If you need clarification, my email address is maxberan@oldboot.demon.co.uk

[someone_somewhere]

Hi Max,
The "guest" was me. I forgot to logon as "someone_somewhere".
And now to business.
The 200+ are true and not. I have 200+ solved all except one, without a computer program.
As input for the program I have only 100+, selected only the "fiendish" and a couple of difficult. The input file is a extreme simple ".txt" as you can imagine. For example:
043080250
600000000
000001094
900004070
000608000
010200003
820500000
000000005
034090710
So I have 100+ such test files.
And now to the program. It first prints the input. Than it works through several "levels". A trace is available, just to show how he is "thinking" and is mainly giving:
- a found number, and why (which combination)
- a number that was excluded from a cell (for the so-called Exclude Table or Candidate Table) and why (which combination).
Everything is in a big loop of trying to find something.
When the lemon was squeezed and no drop falls into the coctail glass,
we have 2 possibility:
- the coctail is ready, initial position is solved. Solution is printed and some statistics.
- not solved. The "Exclude Table" (or left Canditate) is printed and the statistics.
Just to give you a feeling, how the drink tastes (for the above position):

Final SuDoku Table

1 4 3 9 8 6 2 5 7
6 7 9 4 2 5 3 8 1
2 8 5 7 3 1 6 9 4
9 6 2 3 5 4 1 7 8
3 5 7 6 1 8 9 4 2
4 1 8 2 7 9 5 6 3
8 2 1 5 6 7 4 3 9
7 9 6 1 4 3 8 2 5
5 3 4 8 9 2 7 1 6

SuDoku game was solved in 6 LEVELS !!!
Statistics
Initial Numbers= 26
Unique Nr in Cell= 6
in Horizontal Line= 2
in Vertical Line= 44
in 3x3 Squarer= 3
Total Found Numbers= 55
Scan Horizontal Exclude in 3x3= 3
Vertical Exclude in 3x3= 3
Scan 3x3 Exclude Horz & Vert= 3
Scan Horiz 2 Nr Exclude other Nr= 0
Vert 2 NR Exclude other Nr= 4
3x3 2 Nr Exclude other Nr= 0
Scan Horiz 2 Nr Exclude same Nr= 10
Vert 2 Nr Exclude same Nr= 0
3x3 2 Nr Exclude same Nr= 0
Scan for Vertical X-wing Nr= 3
Horizontal X-wing Nr= 3

Of any help? I did not disclose a lot, but at the moment I have "only" 2 positions that are not solved by the program. The check program from this site tells me that it will need a "look ahead" for them.
So I am interested in the most, almost difficult, almost impossible (even not symetric) positions for improving the program and for developing the "difficulty" calculation.

see u,

[someone_somewhere]

[Max Beran]

Dear someone-smewhere

Obviously I misunderstood what you were offering. What I thought was that you were prepared to use your program to calculate some difficulty indices that people might think up.

I'm responding to your other theory about candidate scores and filled cells on the other thread that you began for it.

Sorry about the confusion. I'll just have to do it for myself.

Max Beran

[Max Beran]

Dear someone-somewhere

That other thread seems to have been pulled so I'll talk about your formula for predicting candidate scores here. Basically it doesn't work. As I mentioned in an earlier message, there is a 0.95 correlation between the number of filled cells and candidate score; it would be 1 if there was a simple formula like yours relating the two. Anyway, the numbers it predicts for candidate scores is at least two times too high.

As an example I sorted some puzzles with 29 filled squares. Candidate scores vary from 159 to 207. Your formula gives 477.