Shortest proofs by contradiction / puzzle hardness

darq

Hi all,

I've just finished first stage of my solver that's intended to give shortest proofs by contradiction for hard puzzles. Currently the solver can find the shortest proofs in terms of number of guesses and show which candidates can be examined to provide a proof. I'm going to extend it so it'll be able to show the exact logical steps constituting the shortest proof path. (probably in September, after going back from holiday)

Results I gained so far make some interesting points in discussion on hardness rating. 3 most interesting:

Merri · Posted: Wed Aug 17, 2005 10:00 am Post subject:

Hardest is the one which takes the most time to solve... of course! In my case this means the last tilps puzzle, which took 0,4 ms. The middle one took only 0,195 ms and the menneke.no 0,15 ms. So yes, my solver is only doing its work computer speedwise, ie. it tries to solve any sudoku as fast as possible. Thus it is a backtracker with three simple logics which are fast to calculate with computer. Times vary from 0,02 ms to about 6 ms.

Probably the other ones are trying to find a "human scale difficulty", which is a bit out of my interest. There are too many humans out there. It would be better to make a program that measures how good someone is in solving a sudoku so it tells a personal difficulty level for the given puzzles. So yes, it would alter the difficulty levels based on what the player is good at. If the player is bad in some kind of solving, then a difficult puzzle would include that kind of a problem...

dukuso · Posted: Wed Aug 17, 2005 10:10 am Post subject:

your program is certainly useful to explain sudoku-solution-paths
to the audience !

But for measuring hardness there are other factors to be considered
too. Does it make sense to search for these shortest proofs
or will this waste too much time in the other puzzles
so the total running time on a random set of puzzles
increases ??
I made the experience, that puzzles can require 5-10
times more computer-solution time, depending on just
how you rotate/reflect the ruzzle before solving it,
but examining what is the best orientation is nevertheless
too much waste of time in average.

So, that would be interesting to see some statistics of your solution times.
And how your hardness measure correlates with others
on a larger sample.
E.g. I put my list of 100 hardest here: (ordered)
http://magictour.free.fr/top100
others have reported that they get completely
different orderings of hardness here.

Guenter.

darq · Posted: Thu Aug 18, 2005 9:52 am Post subject:

Merri,

I agree there is no single human difficulty measure that would be perfect for everyone. But still we tend to look for such ratings, there are plenty of them around. I just wondered how can we prove a guess for hard puzzles, and also - "how hard" a guess is. There are many aspects in rating a puzzle, and guess-proof hardness can be one of them. For me it is (as far as human hardness measure is concerned).

Guenter,

your top100 definitely shows that computational difficulty and human difficulty are different. Sometimes they vary much, as computers can remember plenty of future states and people can't (this is also why I prefer contradictions over lookaheads). I've examined several puzzles from your top100, on both sides of the list are puzzles that can be solved in a step-by-step manner, and they are generally considered easier for humans than those which require trial-and-error. And since I'm interested in human-scale measure, and human-understandable proofs, my program operates in this field. And it seems I'm not the only one interested in such proofs.

Of course search for the shortest proofs increases drammatically running time, but my solver is not meant to be a speed-competitor. Moreover, sometimes an easier puzzle produces bigger search space and thus takes longer to compute. Running times vary much, e.g. 1.75 ms for your top1 and 0.75 for top100 up to over 2 seconds! (divide these number by 4 to scale for modern computers). But time is not a key factor for my solver as it's targeted at points (1) and (b) Doug Bowman gave here. I think I'll refrain from producing total hardness measure, the solver will just give an estimation of proof hardness.

dukuso · Posted: Thu Aug 18, 2005 10:59 am Post subject:

Darq wrote:

>Merri,
>
>I agree there is no single human difficulty measure that would
>be perfect for everyone. But still we tend to look for such
>ratings, there are plenty of them around. I just wondered how
>can we prove a guess for hard puzzles, and also - "how hard"
>a guess is. There are many aspects in rating a puzzle, and
>guess-proof hardness can be one of them. For me it is (as
>far as human hardness measure is concerned).
>
>Guenter,
>
>your top100 definitely shows that computational difficulty
>and human difficulty are different.

does it ? Doug in the thread you quoted below said that they correlate well.
But I found that even different solvers perform quite different on
that list or any other list of "hard" puzzles. I haven't yet asked
humans to rate the puzzles.
My hardness-measure and e.g. Merri's have correlation coefficient 0.37 here.
When I just rotate the sudokus in that list by 180', then I get
a correlation of only 0.16 with the same program !
When you send me your 100 ratings, I'd like to compute our
correlation coefficient. Or yours vs. Merri's.

>Sometimes they vary much,
>as computers can remember plenty of future states and people
>can't (this is also why I prefer contradictions over lookaheads).

memory is not the problem here. You rarely have nested loops
of depth more than 5-10. Humans could do it with photo-copying
or using helper-software.

>I've examined several puzzles from your top100, on both sides
>of the list are puzzles that can be solved in a step-by-step
>manner, and they are generally considered easier for humans
>than those which require trial-and-error. And since I'm
>interested in human-scale measure, and human-understandable
>proofs, my program operates in this field. And it seems I'm
>not the only one interested in such proofs.

Yes. I'd noticed that even Mathematicians write papers now
about this "backtracking-free-solving" ! (Eppstein,Simonis)

>Of course search for the shortest proofs increases
>drammatically running time, but my solver is not meant
>to be a speed-competitor. Moreover, sometimes an easier
>puzzle produces bigger search space and thus takes longer
>to compute. Running times vary much, e.g. 1.75 ms for your
>top1 and 0.75 for top100 up to over 2 seconds! (divide these
>number by 4 to scale for modern computers). But time is not
>a key factor for my solver as it's targeted at points (1) and
>(b) Doug Bowman gave here. I think I'll refrain from producing
>total hardness measure, the solver will just give an estimation
>of proof hardness.

Suppose, ten of my puzzles can be solved in half the time
with "step-by-step", but this increases the average running
time by 20% - then it won't make sense to implement it.

In principle IMO there should be no difference between
human-rating and computer speed.
When there actually is one then it's because computer programs
are not good enough (programmers optimize their implementation
times as primary goal, running time of the program comes only 2nd or 3rd !)
and because humans are not yet good enough at simple backtracking.
Or just don't like it.

Guenter

darq · Posted: Fri Aug 19, 2005 10:16 pm Post subject:

> When I just rotate the sudokus in that list by 180', then I get
> a correlation of only 0.16 with the same program !

Does it mean that correlation coefficient can be easily manipulated? Shouldn't puzzle rating be invariant of group operations?

> When you send me your 100 ratings, I'd like to compute our
> correlation coefficient. Or yours vs. Merri's.

In fact I don't currently have any ratings, but when I get to it, it'll be interesting to compare them. Though, as I wrote before, I'll be rating just guess hardness, not total puzzle hardness.

> In principle IMO there should be no difference between
> human-rating and computer speed.

But why? We know very well that human brains operate differently from computer processors. What is a trivial task for a machine - e.g. performing an arithmetical operation on 2 floating-point numbers - can be difficult for humans. On the other hand - a chess playing program that would not take advantage of knowledge base gained by humans, would be just weak.

> humans are not yet good enough at simple backtracking.
> Or just don't like it.

And that's my point - people don't like it. Because most of them consider it hard. E.g. I prefer to see a logical explanation of all steps I take during solving sudoku. When backtracking with branched paths is involved, it's hard for me to see the big picture - so I find such a puzzle hard. Like puzzle #42 from your list, for which there is no unbranched proof by contradiction (which forces me to extend my solver :)

dukuso · Posted: Sat Aug 20, 2005 5:45 am Post subject:

>> When I just rotate the sudokus in that list by 180', then I get
>> a correlation of only 0.16 with the same program !
>
>Does it mean that correlation coefficient can be easily manipulated?
>Shouldn't puzzle rating be invariant of group operations?
>
>> When you send me your 100 ratings, I'd like to compute our
>> correlation coefficient. Or yours vs. Merri's.
>
>In fact I don't currently have any ratings, but when I get
>to it, it'll be interesting to compare them. Though, as I
>wrote before, I'll be rating just guess hardness, not total
>puzzle hardness.

avoiding guesses could be too expensive

>> In principle IMO there should be no difference between
>> human-rating and computer speed.
>
>But why? We know very well that human brains operate differently
>from computer processors.

i.e. slower

> What is a trivial task for a machine -
> e.g. performing an arithmetical operation on 2 floating-point
> numbers - can be difficult for humans. On the other hand -
> a chess playing program that would not take advantage of
> knowledge base gained by humans, would be just weak.

that's because the program isn't yet strong enough.
Tricks used by humans are often not included because
it's tedious to implement them.

>> humans are not yet good enough at simple backtracking.
>> Or just don't like it.
>
>And that's my point - people don't like it. Because most
>of them consider it hard. E.g. I prefer to see a logical
>explanation of all steps I take during solving sudoku.
>When backtracking with branched paths is involved,
>it's hard for me to see the big picture - so I find
>such a puzzle hard. Like puzzle #42 from your list,
>for which there is no unbranched proof by contradiction
>(which forces me to extend my solver :)

when this sudoku-craze goes on and there are
championships etc., then I assume that the
best human sudoku-solvers will at last use
backtracking almost as frequently as computers do.
It would be helpful to solve it on computer then,
so you can go back to the last furcation easily once
you encounter a dead end. With pencil and paper
you might want to use a different color for each
level of backtracking, so you can locate and erase
the last path.

Guenter.

angusj · Site Admin

dukuso · Posted: Sat Aug 20, 2005 7:18 am Post subject:

craze: pardon my bad English, I just pick the expressions which I meet...
but I assume you know, what I mean.
championship: but there are also human-fast-solving championships
or tournaments with judges, not online, but in halls with spectators
or in closed rooms with jurors.

someone claiming he were world-record-holder:
http://www.sudoku.com/forums/viewtopic.php?t=1206

Israelian championship:
http://www.sudoku.com/forums/viewtopic.php?t=1265

maybe someone finds an interview, about which techniques they use ?

angusj · Site Admin

Moschopulus · Posted: Sat Aug 20, 2005 8:58 am Post subject:

darq · Posted: Sun Aug 21, 2005 9:31 am Post subject:

dukuso · Posted: Sun Aug 21, 2005 1:37 pm Post subject:

but when it comes to the special task of solving 9*9-sudoku puzzles,
then I think the best humans and the best computers
will operate similarly.
An optimal strategy for computers will also be an optimal strategy
for humans and vice versa.

In principle it's also the same with chess-computers,
just that all the human tricks are not yet implemented...

Merri · Posted: Sun Aug 21, 2005 4:41 pm Post subject:

But... the thing is that with computer the approach will tell how quickly the task gets done. Using computer you can push the information to very tiny space and operate it quickly, using certain methods. The code I have isn't targetting to be superior as an algorithm, it is targetting to be fast: move the least memory it can, use the fastest math a CPU can perform. So I have chosen logics that are fast to calculate using math and which require less moving of memory.

You can't emulate that with human brains as it is. Thus, algorithm speed shouldn't be used for rating difficulty for humans. I should add a difficulty counter to my code so that it gives or emulates a human-like rating to the logics the code uses. And... it should gather statistics and analyze the board a bit more, so that instead of quitting immediately when it finds a solution it should look for the additional ways that lead to a failure, so that it can see how much complexity there is in the board in total which confuses a human player.