and now the 25*25

frisch · Posted: Wed Nov 23, 2005 3:25 pm Post subject:

Faster than what ?

I changed the benchmark methodology: the same process does all the puzzles in turn, thus avoiding startup time. Beforehand, I had a script calling the solver for each puzzle.

frisch · Posted: Wed Nov 23, 2005 3:27 pm Post subject:

Here is a minimal 25x25 puzzle obtained from one in the list:

dukuso · Posted: Wed Nov 23, 2005 3:35 pm Post subject:

6.3 times faster than mine.

possible reasons:
1) your program is faster than before
2) the instances were chosen to be hard for my solver
3) my learning heuristics is better on long runs, else there
is not enough to learn

I ran it again with stopping after the solution is found.
Was 1.8 times faster

frisch · Posted: Wed Nov 23, 2005 3:38 pm Post subject:

If I stop after the first solution:

frisch · Posted: Wed Nov 23, 2005 5:42 pm Post subject:

This one is quite hard for my solver. I don't know whether it is minimal or not:

dukuso · Posted: Thu Nov 24, 2005 10:02 am Post subject:

that one took me 36 minutes.
Satz -s : 15 minutes
Satzoo -no-rand -no-static : 5 min.
for finding the solution. I go for this timing now, since the SAT solvers
only report whether an instance is solvable or not

I did another timing which clearly showed Alain,Satz,Satzoo
better than my program, don't know why my earlier measurements
were different.

Here is another set of 50 random QWHs of order 35 and 196 holes:
(I tested it before without switches for Satz,Satzoo)
http://magictour.free.fr/qwh35

I get worse timings than in the paper for Satz and Satzoo i.e. the
6Gcycles per puzzle for Satz, I can't reproduce.
Satz:42s
Satzoo:18s
Guenter:104s

frisch · Posted: Thu Nov 24, 2005 10:05 am Post subject:

Btw, it took 38 minutes for my solver to solve the puzzle posted above (checking for all solutions).

dukuso · Posted: Thu Nov 24, 2005 11:00 pm Post subject:

my timings are worse now compared with Satz,Satzoo,Alain,xyzzy
maybe 2-10 times worth.
But let me briefly describe the simple method nevertheless:

Whenever I backtrack, I increment a counter N1[i][c]
where c is the used constraint (out of the 4*N*N for sudoku,
3*N*N for QWH) and i is the actual number of placements
=filled cells.

Then, when there are ties I prefer those constraints with
maximum counter for that number of filled cells.

Instead of i I take i/16=i>>4 or for N=25: i>>6,
so several numbers of givens are grouped into one counter

This is very easy to implement for DLX

frisch · Posted: Fri Nov 25, 2005 6:40 am Post subject:

It seems to me that our timings are rather close, aren't they?
36 minutes for you, 38 for me...

Here is my latest minimized 25x25 fresh from this night, with 273 clues:

dukuso · Posted: Fri Nov 25, 2005 6:54 am Post subject:

thanks for the minimal 25*25 sudokus. Now we have 5 of them.

My other measurements suggest that my timings are worse,
the 36 minutes was only to find the solution and your's was
complete search. I did another run with a modified program which took
more than an hour. This was with the strategy described above,
the parameters can probably be improved.

It seems to me, that we just have to ensure some clustering
of the placements. It doesn't make sense to place the clues
homogeniously over the board, concentrate on regions and
complete these ! How can it be implemented best ?

frisch · Posted: Fri Nov 25, 2005 7:07 am Post subject:

frisch · Posted: Fri Nov 25, 2005 12:34 pm Post subject:

Some more:

kranser · Posted: Fri Nov 25, 2005 4:52 pm Post subject:

Thanks for all the difficult 25x25 puzzles!
One question though: For all of these puzzles, my solver finds basic patterns (hidden/naked singles, twins, triplets, etc...) and locked candidates, and then reports that it is unable to solve the puzzle without finding any X-Wings, Swordfishes, Forcing Chains, Colouring, XY-Wings. I've not implemented anything more advanced than these techniques yet though, but was wondering if it's normal for these puzzles not to require any advanced techniques (except the really advanced ones like Trial and Error!), or is my solver at fault?

Kranser.

frisch · Posted: Fri Nov 25, 2005 4:57 pm Post subject:

I'm not sure to understand the question. The solver used to minimize the puzzles does not try to create puzzles which are still solvable with only "logic".

You are surprised that your solver does not find any "complex" patterns once all the basic patterns have been applied. Is that right? I have no explanation for this fact.

kranser · Posted: Fri Nov 25, 2005 5:21 pm Post subject:

Yes that is correct frisch - I am puzzled that I was not able to find any advanced patterns in the puzzles you generated.

I would have expected a few XY wings and/or forcing chains to be found even if they did not lead to the solution of the puzzle.

Could this fact have anything to do with how they were generated, or am I wrong and they are in fact some XY wings in the puzzles listed?

Kranser.