The New Sudoku Players' Forum

[Moschopulus]

The only chance i see is to run CHECKER and wait until it has finished. I dont know, how fast Moschopulus' solver is, maybe he should give gsf's solver a try.

CHECKER currently uses dukuso's solver. As gsf said, he is trying his own solver instead and it seems to improve things.

The running time of checker depends on several things, not just how fast the solver is.

I am working on another improvement, adding more unavoidables.
---------------

Hi gsf: interesting about the other improvement. It would be good to have your solver!

The guys are looking for an 18 in this grid
146328975785196342329457861493561728218973654657284139564839217832715496971642583
but we don't know if one exists.

This grid
937856241562194387481273569823647915615932478749581623378469152196725834254318796
we know has a 19 but no 18. Searching for a 19 or a 20 in here might be a good test. A 21 is found immediately.

[gsf]

Hi gsf: interesting about the other improvement. It would be good to have your solver!

The guys are looking for an 18 in this grid
146328975785196342329457861493561728218973654657284139564839217832715496971642583
but we don't know if one exists.

This grid
937856241562194387481273569823647915615932478749581623378469152196725834254318796
we know has a 19 but no 18. Searching for a 19 or a 20 in here might be a good test. A 21 is found immediately.

it found this 20 for the 93* grid in 21 min on a 3.2Ghz pentium
930000200002004300000070560800600000000000478000501000000000000100000004050300000
19 search underway

[Moschopulus]

it found this 20 for the 93* grid in 21 min on a 3.2Ghz pentium
930000200002004300000070560800600000000000478000501000000000000100000004050300000

Thanks. Please could you compare the 21 min time to when you run the old version of checker on the same computer, compiled with same compiler, etc. That way we get the best comparison.

[gsf]

it found this 20 for the 93* grid in 21 min on a 3.2Ghz pentium
930000200002004300000070560800600000000000478000501000000000000100000004050300000

Thanks. Please could you compare the 21 min time to when you run the old version of checker on the same computer, compiled with same compiler, etc. That way we get the best comparison.

the original on that machine found this 20 in 65 min

Code: Select all

930000200002004380000070500800600010005900400000080000000000000000025000000000096


the 19 is chugging away, just passed 1.2G puzzles
shall I post a tarball with my changes or do you want it via email
so you can double check and possbly post on your site?

[Ocean]

This grid
937856241562194387481273569823647915615932478749581623378469152196725834254318796
we know has a 19 but no 18. Searching for a 19 or a 20 in here might be a good test. A 21 is found immediately.

Just for a reference: Maybe it's interesting to compare the running times to a simple random approach, which needed roughly 500000 'solver-calls' (and 20 'manual' input preparations) to find the first 19. Further search found 100+ different 19s (accompanied by 6000+ 20s).

The 100 first found 19s for this grid:
937856241562194387481273569823647915615932478749581623378469152196725834254318796
#
000000001000090300080200000000007005600000470009081000370400000100000000000000096
000000001000090300080200000000007900000000470009081000370400000100000000000010096
000000001000090300080200000000007900000000470009081000370400000100000000000300096
000000001000090300080200000000007900000030470009081000370400000100000000000000096
000000001000090300080200000000607005000000470009081000370400000100000000000000096
000000001000090300080200009000007000000000470009081000370400000100000000000010096
000000001000090300080200009000007000000000470009081000370400000100000000000300096
000000001000090300080200009000007000000030470009081000370400000100000000000000096
000000001000090300080270000000000005000000470009081000370400000100000800000000096
....
[Edit: The post was too long... it's enough to list a few...]
....
900000001000004080000200069023600000005000400000081000000000000100000004050300700
900000001000004080000200069023600000005000400000081000000000000100700000050300006
900000001000004087000200060023600900005000400000081000000000000100000004050300000
900000001000090000080200500003000000000000470009081000070400000100000800000300096
907000000000000080400200009023040000005000070000081000000000100100000004050300700
930000001000000080400200009000000000000000470009081000008409000106000000000300700
#

[Moschopulus]

Just for a reference: Maybe it's interesting to compare the running times to a simple random approach, which needed roughly 500000 'solver-calls' (and 20 'manual' input preparations) to find the first 19. Further search found 100+ different 19s (accompanied by 6000+ 20s).

Yes, although I would not expect checker to compete well with a random search in general. Checker was not really written to find puzzles. It was written to do an exhaustive search through a grid. It's really written to definitively answer the question "does this grid have a 17", or a 16 or 18 or whatever. A random search can answer yes to this question, but it can never answer no.

Having said all that, gsf is improving the speed of finding puzzles.....

[coloin]

Code: Select all

.....8...7.5.......2......1....6......8....54..72......6..3.21.8..7.5...........3

One more 19 in "grid 3" !

[gsf]

This grid
937856241562194387481273569823647915615932478749581623378469152196725834254318796
we know has a 19 but no 18. Searching for a 19 or a 20 in here might be a good test. A 21 is found immediately.

the 19 search completed over the weekend
it was generating and solving ~8000 puzzles/sec/Ghz

Code: Select all

It appears the following 19 clues uniquely determine the grid:
900800200000000087401000000003000015000900400700080000000060000006025000000000090

real    51h20m41.59s
user    51h21m3.10s
sys     0m1.22s


[Moschopulus]

the 19 search completed over the weekend
it was generating and solving ~8000 puzzles/sec/Ghz

Wow! So on a P4 3Ghz you were doing 24,000 puzzles per second. That's fast!

I shudder to think how long our version of checker would take.

It would be interesting to compare this with a random search. (Ocean?)

[Ocean]

the 19 search completed over the weekend
it was generating and solving ~8000 puzzles/sec/Ghz

Wow! So on a P4 3Ghz you were doing 24,000 puzzles per second. That's fast!

I shudder to think how long our version of checker would take.

It would be interesting to compare this with a random search. (Ocean?)

I am very much impressed by the speed of puzzle generating and testing! The 24,000 puzzles per second can be compared to my slow soft/hardware which generates about 10 minimal sudokus per second (when each minimal requires 20 tests). That is about 200 tests per second. A speed factor of 120 in favour of the modified checker.

The random perturbation with feedback method found the first 19 after printing about 20,000 sudokus. (requiring about 500,000 tests). Compare this to the complete search method, when a 19 was found after testing 4.4 G puzzles (if my estimates are correct).

In terms of time: If gsf's new solver were used, and on the fast hardware, it would take about 30 seconds to find the first 19 by the random perturbation method. Compared to 51 hours of the complete search process. That is a time factor of 6,000 in favour of the random method, for this specific search on this specific grid. On my slow machinery the process took maybe one hour machine time - still a factor 50.

Now, the advantage of complete search over random search is also obvious: You are guaranteed to find what you look for (a 19) if it is there. While there is no such guarantee for the random process. Interestingly, the specific 19 found by checker was not among the (first) 114 19s found by the random method.

In the long run, a complete search method will always beat a random method. But why not also from the very start? 51 hours compared to 30 seconds is a rather slow start - which suggests there might be room for improvements...


PS.
Without knowing the inner part of checker, here are two different suggestions - not necessarily trivial - 1. Is it possible to select some specific orders of which puzzles are tested, in such ways that early hits are more likely? .... 2. Is it possible to 'check out' large groups of puzzles (instead of testing each one, but still guaranteeing there is no hit in that group)?

[gsf]

I am very much impressed by the speed of puzzle generating and testing! The 24,000 puzzles per second can be compared to my slow soft/hardware which generates about 10 minimal sudokus per second (when each minimal requires 20 tests). That is about 200 tests per second. A speed factor of 120 in favour of the modified checker.

I think I clarified my checker mods offlist to M
its has two modes
the first does a quick search that solves most puzzles without backtracking
this is the mode that took 51 hours
it skipped over the puzzles that would have required backtracking
I didn't keep a count of those but will do so and run the 51 hr params again

the other point is that the checker generator generates candidate puzzles
with a set number of givens which is different than a
generator that generates minimal puzzles (the latter would take more time)

the solver options I used in checker did not check if the hit grid was minimal
but given the application (looking for minimal # givens) this is probably not a problem

[dukuso]

sorry, if I didn't read all the posts.
AFAIR gsf's solver was almost 10 times faster than mine
some months ago for normal(easy) 3*3 sudokus.
Maybe that gives checker a factor of upto 10 by mere optimization.

I didn't understand the 6000-factor thing.
Is it now meanwhile feasable to search grids for a 18 or 19 in a few minutes ?

[dukuso]

sorry, if I didn't read all the posts.
AFAIR gsf's solver was almost 10 times faster than mine
some months ago for normal(easy) 3*3 sudokus.
Maybe that gives checker a factor of upto 10 by mere optimization.

I didn't understand the 6000-factor thing.
Is it now meanwhile feasable to search grids for a 18 or 19 in a few minutes ?

[Ocean]

I think I clarified my checker mods offlist to M ...

Thanks for the information (and for providing the solver!). I might try to play with it and see what difference it makes.

I didn't understand the 6000-factor thing.
Is it now meanwhile feasable to search grids for a 18 or 19 in a few minutes ?

OK: The method I used resulted in a 19 in about one hour running time (plus some manual feedback during the process). This was 50 times faster than the 51 hours spent by the fast version of checker. The fast version of checker apparently runs 120 times faster than my program (combined effect of faster solver and faster machine). 50*120=6,000. The factor 6,000 simply represents the number of times the program called solve() to check if a candidate puzzle is a valid sudoku. (500,000 times vs. 3G or so?)

A few important things: When a method is based on random search (or random perturbations), there is never a guarantee to find anyting at all. In the long run a complete search will always win.

Still, I don't think the early finding of 19s can be pure luck only. But true, the factor 6,000 is very unrelyable, based on one case only. Some 'repeted runs' would show quite different factors even for one grid, and certainly for different grids. (The manual feedback involved allows different strategies to be applied, but complicates 'independent testing' and statistics.)