Nodes per second

abik · Posted: Sat Sep 10, 2005 4:28 am Post subject: Nodes per second

Because I just wrote a simple Sudoku solver, I was wondering what the approximate state-of-the-art search rate in nodes-per-second is? I was able to search about 9.6 million nodes-per-second on a 3GHz Pentium 4 processor (see http:/www.aartbik.com/MISC/sudoku.html for some details) with a straightforward backtracking algorithm that visits nodes in increasing order of remaining possibilities. Are there any benchmarks for the quality of solvers that balance the quality of pruning the state space vs. the raw nodes-per-second rating?

dukuso · Posted: Sat Sep 10, 2005 6:26 am Post subject:

I have ~200000 nodes per second,
where a node is a placement of a digit.
I use only the 324 basic constraints,
usually called "naked single", "hidden single" here.
How long do you need to solve the puzzles from :
http://magictour.free.fr/top95
me:0.15s with 2.6GHz

abik · Posted: Sat Sep 10, 2005 7:08 am Post subject:

The link does not seem to work. I typically use an "underspecified" puzzle with many solutions to test raw nodes-per-second speed. An example follows. How much time does your solver take to go through all these?

dukuso · Posted: Sat Sep 10, 2005 7:22 am Post subject:

Nick70 · Posted: Sat Sep 10, 2005 9:26 am Post subject:

I fit in the middle with 7.5 seconds on a P4 2400 using vanilla Knuth's dancing links.

dukuso · Posted: Sat Sep 10, 2005 9:49 am Post subject:

what language, what compiler, what CPU ?

you get a factor of 2 just because you let the links dance ?
(mine are static)

Nick70 · Posted: Sat Sep 10, 2005 2:22 pm Post subject:

dukuso · Posted: Sat Sep 10, 2005 3:04 pm Post subject:

Nick70 · Posted: Sat Sep 10, 2005 4:55 pm Post subject:

abik · Posted: Sat Sep 10, 2005 6:58 pm Post subject:

I was able to optimize the raw speed of the solver a little more (see below). On the top 95, I was not doing so well due to the time it takes to read the puzzles from file. How is the typical benchmarking done (read the puzzles from file/stdin or memory, and then output the solutions or just count them)?

dukuso · Posted: Sat Sep 10, 2005 7:57 pm Post subject:

for me time needed for input and output is almost negligable,
but for you it could be different.

Well, assume the sudokus are in memory, then start the clock,
count the solutions, stop the clock.

Many puzzles are better for benchmarking, because
solvers can differ a lot on single puzzles due to
ordering of the constraints.

abik · Posted: Sat Sep 10, 2005 10:01 pm Post subject:

The IO was indeed not really the performance bottleneck: my solver does not reach peak nodes-per-second rating for several single-solution puzzles but, more importantly, probably considers too many nodes due to the simplicity of pruning. Can you please show the total number of nodes considered by your solver for the whole tour, so we can compare if your pruning algorithm is superior?

dukuso · Posted: Sat Sep 10, 2005 11:34 pm Post subject:

66000 nodes, can be 50000 or 80000 on the same puzzles rotated.
these are collected hard puzzles.

You can also try the 1011 instances from the contest:
http://magictour.free.fr/msk_009
for a more random sample of sudokus.

114000 nodes and 0.3s with 2.6 GHz here,
counting the solutions.

abik · Posted: Sat Sep 10, 2005 11:44 pm Post subject:

The solver does much better here
(by the way, reading in data is included in timing as well now):

dukuso · Posted: Sat Sep 10, 2005 11:54 pm Post subject:

you still have 8 times more nodes here than me,
while in earlier examples with multiple solutions
it was almost the same

here are the timings from the contest with 2.5GHz,
subtract 50% or such for poor in/output timing
finding the solution was sufficient