let's merge our ideas/programs into a best, common solver !

dukuso

I don't want to implement all these rules ...
Can't we do something which "includes" all the rules even if
it's a bit slower ?

Or better: is there a downloadable list of sets to test ?
We have a 9*9*9 ternary(0:allowed,1:forbidden,2:already placed)
array of placements (x,y,s) whether symbol s can go into cell (x,y).
As one rule, assume we have a subset of size -say- 6 of this 9*9*9.array ;
if its sum is -say- 5 , then we have another subset which can
be marked 1 (forbidden).
Now, let's make a list of all these (subset,sum,subset)-triples
which have to be checked ! Can your program generate them ?
Then that list can be easily included to improve and simplify
other solvers.

Whenever you have to guess, then it's likely that there are just
only two possibilities.
Check both of them, but this time only by making forced moves,
no further (2nd-level) guesses.
If one of the two possibilities leads to a dead end (=contradiction),
then we can choose the other one as a forced placement.

More generally :
use lookahead of level L to determine which of
the bifurcations (only 2 digits possible in row.column,block,cell)
have the fewest nodes at distance L from the bifurcation-centre.

L is adapted dynamically depending on the average number
of bifurcations and nodes, so that the total time spent
at distance k from a bifurcation is almost konstant(k).

I'm not so much concerned about the 9*9
puzzles here but about the larger ones 16*16,25*25,...
Yes, it's NP-complete but let's see how good we can do
here compared with other NP-complete problems.
The 9*9-case with all these rules is pretty well solvable,
at which level do the real problems arise ?

Guenter.

hoppy · Posted: Sat Jul 23, 2005 11:00 am Post subject:

The brute forcing methods just have to check the basic game rules - all squares must appear in each individual row/col/block.
The other tests such as looking for groups of numbers are used when attempting to solve with logic (no guessing or looking ahead - just rule out possibilities - and fill in numbers as the become certain).
This brute force method should work for larger grids, there are constants defined for grid & block size:
http://www.users.waitrose.com/~nihilist/sudoku.html

dukuso · Posted: Sat Jul 23, 2005 1:51 pm Post subject:

I convinced myself that the best method to write a solver is to
use the dancing links method - but without keeping the whole
4*n*n * n*n*n binary matrix, only the 4 nonzero entries
per row and the 9 nonzero entries per column.
I hope that's possible ?!

And then, always do forced placements immediately.
And check for bifurcations(= 2 possible placements), where
one way leads to a dead end (=contradiction) when filling
in the forced forced placements.
Call such bifurcations "forced placements of level 2".
This should include all the other rules with x-wing, disjoint subset,
etc. They are all forced placements of level 2.

We could extend this to bifurcations, where one way leads
to another bifurcation with two dead ends etc.
I wonder, whether that's what tilps is doing with his
ratings like 1.3.2

tilps · Posted: Sat Jul 23, 2005 2:32 pm Post subject:

dukuso · Posted: Sat Jul 23, 2005 3:10 pm Post subject:

>>I convinced myself that the best method to write a solver is to
>>use the dancing links method - but without keeping the whole
>>4*n*n * n*n*n binary matrix, only the 4 nonzero entries
>>per row and the 9 nonzero entries per column.
>>I hope that's possible ?!
>
>
>if you actually have the zeros at all then you arent actually
>doing dancing links, the speed of dancing links comes from not
>having the array at all, but from storing all the '1's' in multiply
>linked objects. See antony's source code over in the setting sudokus
>section.

you're probably right. I'll search for antony's code.
We might need a modified dancing links because we have a special
array which could speedup some things. And we want to keep
track of the constraints to report the solution-way with rows,cols,
blocks to readers.

>If you want to do something which 'includes' all the rules, then
>you want to do what I am doing probably, runtime generated
>constructive logic.

whatever that is..

>You find possibility pairs/tripples/quadruples/etc in the puzzle,
>and perform find the common eliminations that can be generated
>using simple logic on each branch of the possibility n-tuple.
>You can then reduce the set of changes on each branch down to
>just the ones needed to cause the elimination, which will show
>you the information you need to explain the 'logic rule' which
>has been used, to someone else.

which can be done in different ways. IMO the simplest is the way
explained in my previous post.

>My rating system is an attempt to classify the logic rules generated
>in a 'basic' order of difficulty.

which depends on your subjective classification. While I claim
that my classification is more "canonical". You just measure
the degree of bifurcation or lookahead in a well-defined
search-tree. Just graph-theoretical parameters.

>Within each rating classification there are easier and harder ones,
>and there is probably some overlap between the classifications themselves,
>but as an overal concept, they show an order of difficulty.

that's the problem. Others might have other interpretations of overlap

>Rating 0 puzzles are trivial
>Rating 1.0.2 and 1.0.3 are solvable by most reasonable sudoku solvers.
>Rating 1.1.2 is where the puzzles start to become 'interesting',
>tricks like xwing and xy-wing start to come into play.

in my rating there is no difference between these terms.Why should
e.g. "x-wing" be more or less difficult than "forced chain" ?
It's both just lookahead of level 1 : assume a placement, make
forced moves, see if you get a contradiction (dead end).

>Locked doubles fall into this category.

I don't know locked doubles or xy-wing ATM. Maybe I should/will look
it up..

>Rating 1.2.x puzzles are all pretty much only for super-puzzle solvers.
>(My financee managed to solve rubylips 48-unwind puzzle by hand using
>logic ... I was impressed)
>1.3+ is insane. (well, i havent given any of those to my fiancee yet,
>may turn out humans can do those too...)

depends on the time which you invest

>Rating 2 is for where logic is not enough to find a common elimination,

you just have to increase the lookahead-level. Well, depends on how
you define "common elimination"

>and that common elimination techniques need to be performed on
>possibility pairs/triples/etc within the branch already being looked
>at in order to generate common elimination on the current branching point.
>Rating 2 is needed for locked tripples. I have found no evidence that
>rating 2 is needed for 3x3 puzzles. It may be needed for 4x4, I am
>investigating that now. Other than locked tripples, I dont see any
>human ever being able to actually use this level of logic.

given enough time he will.

Once I implemented my lookahead-rating, I'll try to generate
harder sudokus...

Guenter.

jaap · Posted: Sat Jul 23, 2005 10:23 pm Post subject:

tilps · Posted: Sat Jul 23, 2005 11:59 pm Post subject:

tilps · Posted: Sun Jul 24, 2005 12:31 am Post subject:

dukuso · Posted: Sun Jul 24, 2005 8:49 am Post subject: