How fast is fast?

Programs which generate, solve, and analyze Sudoku puzzles

How fast is fast?

Postby stivo » Wed Apr 30, 2008 4:19 pm

I'm wondering how fast your solver is? This is the benchmark puzzle I use with my solver:

500000009020100070008000300040600000000050000000207010003000800060004020900000005

My 2GHz Intel Core 2 Duo MacBook can solve it in .093 seconds. The solver is written in C and compiled with optimizations. How fast is yours? I am interested in seeing other people's code as well.

-
STiVo
stivo
 
Posts: 1
Joined: 30 April 2008

Postby champagne » Fri May 02, 2008 1:44 pm

Hi

This is metcalf puzzle, one of the hardest. (top in JPF's list)

It took my solver 79 milliseconds to check unicity, which seems comparable to what you call "solving".

It took the computer (a PC) about 17 seconds to really solve it.
I am using c+ language under windows.

It happens that I am publishing the solution.

The draft is already visible at that point,

http://pagesperso-orange.fr/gpenet/UX/Sample5metc/metc_fichiers/V1_00.htm

Normally, to-day the first half should be clean.

A very interesting puzzle for those who want to crack a very hard puzzle without help of a computer.
champagne
2017 Supporter
 
Posts: 5744
Joined: 02 August 2007
Location: France Brittany

Postby Draco » Thu May 08, 2008 6:59 pm

My solver is written in C# and requires .Net v2. It uses an optimized recursive (aka back-tracking) search to find a solution.

Averaging out 100 runs after a garbage collection, it takes about 6 milliseconds to find a solution to the puzzle. For some reason I do not understand, the same run with a DEBUG build under the debugger (Visual Studio) takes 2 - 4ms per run. Got to love that .Net runtime!

Cheers...

- drac
Draco
 
Posts: 143
Joined: 14 March 2008

Re: How fast is fast?

Postby gsf » Thu May 08, 2008 10:54 pm

stivo wrote:I'm wondering how fast your solver is? This is the benchmark puzzle I use with my solver:

500000009020100070008000300040600000000050000000207010003000800060004020900000005

My 2GHz Intel Core 2 Duo MacBook can solve it in .093 seconds. The solver is written in C and compiled with optimizations. How fast is yours? I am interested in seeing other people's code as well.

that's ~5 puz/sec/Ghz, but you should run the test on say 1000 copies of the same puzzle
and divide the results by 1000 to normalize
my general solver limited to singles and backtracking solves 1000 copies at ~335 puz/sec/Ghz
another 150 line backtracking solver comes in at ~746 puz/sec/Ghz
and a dlx solver just posted on the programmer's forum (not mine) gets ~1190 puz/sec/Ghz

performance varies on input, the new dlx solver does well with smaller number of clues
mine does better with more, e.g., on ruud's top50000
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Speed

Postby Papy » Sun May 18, 2008 6:02 pm

In fact you have two ways to solve a grid using a logical solver or a 'Brute Force' Solver

The logical solder is the faster when it finds!
Brutal solver always find and the times doesn't depends of the difficulty only the clues reparttition.

A test with just a grid is bad. 1000 times also
On my 2,4 Ghz Core 2 I solve the a grid 5000 times in a second but I need two MINUTES with anopther.

Programmer know this problem. You have solutions( sort the grid) but You also needs time to do it.

So to compare your result what kind of solver do you write.


Papy
Papy
 
Posts: 131
Joined: 15 August 2006

Postby cardinal » Sat Oct 04, 2008 11:37 pm

try this one :(no solution)
000760000000400071800000000000000000007000900600300120070000040000006000000970000

some backtracks clogged:D
cardinal
 
Posts: 9
Joined: 04 October 2008

Postby udosuk » Sun Oct 05, 2008 3:07 am

cardinal wrote:try this one :(no solution)
000760000
000400071
800000000
000000000
007000900
600300120
070000040
000006000
000970000

some backtracks clogged:D

That's interesting. Any (smart) solver should immediately recognise that you can't place a 7 on c1. Yet some of them actually struggle to prove it using brute-force. Makes you think about how dumb (some) programs really are.
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby cardinal » Sun Oct 05, 2008 8:35 am

i admit it, when I firstly wrote my solver, got caught in this one:) it was only pure brute force.

after that, I introduced some logic. naked and hidden singles/pairs, line/box interactions.
cardinal
 
Posts: 9
Joined: 04 October 2008

Re: How fast is fast?

Postby zhouyundong_2012 » Sun Feb 12, 2012 9:08 am

My Speed: 0.777 ms UniqAnswer (1.46G CPU)
zhouyundong_2012
 
Posts: 138
Joined: 10 February 2012

Re: How fast is fast?

Postby JasonLion » Sun Feb 12, 2012 12:44 pm

On the original puzzle, my backtracking solver does it in 0.000209 seconds, or about 1,800 puzzles/second/GHz on a Core 2 Duo.

The invalid puzzle runs at over 300,000 puzzles/second/GHz.

A discussion of my solver, with source code, is available over on the programmers forum, http://www.setbb.com/phpbb/viewtopic.php?mforum=sudoku&p=11913. I tried fairly hard to make the code readable, but some of the speed optimizations are fairly obscure.
User avatar
JasonLion
2017 Supporter
 
Posts: 624
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: How fast is fast?

Postby zhouyundong_2012 » Sun Feb 12, 2012 3:46 pm

:lol: your solver is too fast! I should improve it again.
zhouyundong_2012
 
Posts: 138
Joined: 10 February 2012


Return to Software