solver "philosophy"

i_smith · Posted: Tue Apr 07, 2009 3:39 pm Post subject: solver "philosophy"

If you’re interested only in solving a Sudoku with a computer, it seems hard to beat Scott Hemphill’s 2006 solver written in C. It’s very small and very fast, and it appears to solve anything you throw at it. On the other hand, if you’re interested in discovering the clever ideas the author of a puzzle used in creating it, you’d probably want a solver that tries a variety of solution methods and reports their success or failure. You learn nothing about puzzle design from Hemphill’s program, but you do learn something about ruthlessly efficient algorithm design from looking at his code.

Adak · Posted: Wed Apr 08, 2009 7:28 am Post subject:

I just found it. It looks quite fast, with that large look-up table. I'm looking forward to testing it. Have you run any benchmarks or comparisons with this program?

It would be great if we had a sticky post with a full listing of current url's to lots of different types and styles of Sudoku programs. Sorting them by type: backtracking, humanistic, dancing links, combo, etc., would be helpful.

Many of the url's that are in the forum's archive linking to programs, are no longer current.

i_smith · Posted: Thu Apr 09, 2009 6:28 pm Post subject:

Hi (again) Adak,

You must be the only person who reads my posts!

I did run Hemphill's algorithm on a number of puzzles, including the "very hard" set of 30 on the Logic website and all of the legal puzzles on the Programmers Forum. It blazes through all of them in seconds. I assume you know where these pages are. I wasn't allowed to put URL's in my posts.

As I suggested in my last post, Hemphill takes a lot of the fun out of solver programming because his program gives you no information about the design of the puzzles it solves. I plan to run it on available databases of supposedly super-extreme sudokus, but, looking at Hemphill's code, I don't see how it can fail on any valid puzzle, no matter how difficult.

Adak · Posted: Fri Apr 10, 2009 4:32 am Post subject:

I agree, it should not fail. It doesn't appear to be as fast as I was expecting, but it should solve every valid puzzle.

All that formatting and checking stuff is pretty standard in every solver, so I don't believe Scotts program spends much time doing it. In any case, it's a level playing field for all solver's in that respect, so I don't see any advantage to changing any of that.

Of course I'm reading all your posts! It's much easier than re-writing my solver. Rolling Eyes

coloin · Posted: Fri Apr 10, 2009 9:17 am Post subject:

I dont think there is an issue regarding what program can solve what puzzle.

If a puzzle is valid, many solver programs have no trouble what so ever solving any of the extreme puzzles. Admittedly it takes slightly more milliseconds and envolves a few guesses and nodes - but they all get solved quicker than i can blink.

Backtracking will solve all valid puzzles, if its speed your after i suggest you compare it with many of the benchmark lists of puzzles.

C

Adak · Posted: Sat Apr 11, 2009 4:41 pm Post subject:

After a good deal of work, I was able to get Scott's program running in "bulk" benchmark mode.

I gave it the first 1,000 grids in Gordon's 17's list. It solved them all in just 42 seconds, which was better than I expected. I thought it might stumble on them, since there are so many candidates, in so many cells, and it has no other human logic - just brute force.

There was no stumbling by his program, for sure. Smile

Watching his program run, most games were solved in loosely the same amount of time. When I ran my solver through the same grids, it had the *wildest* swings in time - 40 games might go by so fast, your eye never saw the game counter increment.

And then there were game grids like #619! My solver was there so long, I was going to stop it, thinking it had somehow gone South - but finally, *finally*, it did solve it and moved on. What a hellion that #619 is for my solver!!

A few others were like that also, and it's time I found out why my brute force solver function, can get hung up on some of them, so badly.

How did you happen to come across this "classic" program, anyway? It's dated from 2005, were you just rummaging through the archives??

In any case, a good find! Smile

gsf · Posted: Sat Apr 25, 2009 5:16 am Post subject:

i_smith · Posted: Sun Apr 26, 2009 12:16 am Post subject:

I wonder if Adak would share his "bulk processing" code for Hemphill's solver with us? I've tried to write such a program but keep making some stupid error that I can't track down. My own bulk processor was very slow
because I formatted the sudokus from the various databases in an
interpreted language in which I generally don't make stupid programming
errors. The two programs, Hemphill's and mine, interacted through files.

BTW, Adak is right: Hemphill's program dates from 2005, not 2006 as I wrote in an earlier post.