Question on benchmarks

briturner · Posted: Tue Oct 14, 2008 4:31 pm Post subject: Question on benchmarks

Greetings,

This is my first post, but I have been reading posts on and off for a couple months now after writing my Sudoku solver based on automating my manual method.

I have a few questions on benchmarks and puzzles:

First, some background:
I wrote a general purpose Sudoku solver that can handle 3x2, 3x3, 4x4, 5x5, and 7x4 (other sizes are possible, but those are the only test cases I had). It also is designed to handle overlap puzzles of any valid size (including mixed sizes). My biggest test case is 59 overlapping 3x3 puzzles.

My algorithm uses a combination of logically solving, and then guessing and backtracking. I am looking at picking algorithms for fast solving, so I implemented some more logic that eliminated some guessing, but it took longer than just guessing. I also stop once a valid answer is found, so if there are multiple answers, I only find one.

I use straight C (Visual C version 6), and do not use any embedded assembly since that should be the last resort of any optimization (only to be done once all algorithmic optimizations are in).

My first question, is what is considered a good speed for solving? I ran the top1465 through my solver (1.8 GHz laptop, output disabled) and solved them in 0.843 seconds (575 microseconds per puzzle). What do other people get for times?

Secondly, is there any standard set of puzzles for the larger groups (like 4x4 or 5x5, or overlapped puzzles)?

Thank
brit

m_b_metcalf · Posted: Tue Oct 14, 2008 6:36 pm Post subject: Re: Question on benchmarks

briturner · Posted: Wed Oct 15, 2008 12:31 pm Post subject:

Thanks,

I tried plugging in this puzzle, and my solver failed Sad

I use bit masks for part of my solver, and 49 bits overflowed my 32 bit integer. I will need to re-write my solver to handle the larger sizes. My previous puzzles had a max of 28 (4x7), so it was not a problem.

Most my larger puzzles I got out of the magazine which I can't list because I can't post Japanese characters, and I can't link to due to board restrictions. They also have PDFs of overlapping Sudoku you can download off their site. Their magazine has an 8 page fold out with really large puzzles (last month had the 59 overlapping Sudoku, an 8 page slitherlink, and a 3 page Kakuro puzzle).

If anyone is interested in the link to the magazine, or the sample PDFs, let me know any maybe I can private message them. I have a friend in Japan who mails them to me, I can't find anyplace in the US that carries them.

brit

m_b_metcalf · Posted: Wed Oct 15, 2008 2:03 pm Post subject:

Try this one. Takes me 0.3s.

briturner · Posted: Wed Oct 15, 2008 2:31 pm Post subject:

I use ascii art for the results, which don't post well, but this one works (less than 32 bits needed). My solver uses a combination of logic and backtracking. I wrote it before finding these forums, so I just programmed my manual method, nothing real advanced. Here is what I got:

Solved in 0.094 seconds, Max depth of 32.
Calcs = 1922, Guesses = 451.

I have some things to do to my solver now:
- add option to search for multiple solutions
- make an optimized version for 9x9 and 16x16
(just curious how much it helps)
- make a larger than 32 bit version
- improve puzzle import
(I currently have to tweak puzzles to my format)
- provide options to turn on and off different techniques

so, still a ways to go
brit