Backtracking solver by a forum newb

zerothbase · Last edited by zerothbase on Fri Nov 07, 2008 9:12 am; edited 1 time in total

Good day all,

I've been reading these forums for a few months now, but this is my first post.

I created a simple backtracking solver in C, just to see the performance compared with some of the DLX solvers out there (specifically Ignacio's fast_solv_9r2.c). I've done a little bit of optimization but I still have a lot to do, I think, to get near the "big dogs" on the forums like gsf and ignacio_ar for performance. It's about 220 lines of actual code (with comments removed).

v1 - http://tinyurl.com/5jjpl4
v2 - http://tinyurl.com/6krpwl (faster by ~25%)

Similar options to other small solvers: -q for stats only, -s2 to verify uniqueness, or -s# in general to change the max solutions to find.

It will take a puzzle file on stdin or on the command line. Also, if you modify the "#define BOX" line, it will handle 2x2, 3x3, 4x4 or 5x5 puzzles, though I've really only been focusing on 3x3's for testing.

Let me know what you think.

briturner · Posted: Mon Nov 03, 2008 12:59 am Post subject:

It looks very good. I have also found that DLX is fast, but not the fastest (at least not on the 9x9 grids). here are the timings I got on my laptop (all compiled with Visual C 6.0, release configuration for improved optimizations), and timed with ntimer:

Stopping after first solution found:
0:00:05.000 - fast_solv_9r2.c -q < top50000.sdm
0:00:02.750 - zerodoku top50000.sdm -q
0:00:02.000 - BB_Sudoku -t0 < top50000.sdm

Verifying uniqueness
0:00:05.921 - fast_solv_9r2.c -q -s2 < top50000.sdm
0:00:03.781 - zerodoku top50000.sdm -q -s2
0:00:02.671 - BB_Sudoku -t0 -m < top50000.sdm

brit

gsf · Posted: Mon Nov 03, 2008 11:12 am Post subject:

can you normalize your timing results to puzzles/second/cpu-Ghz
thanks

briturner · Posted: Mon Nov 03, 2008 11:45 am Post subject:

Since I am on a 1.83 GHz processor, it works out to be the following:

Stopping after first solution found (Puzzles/second/cpu-Ghz) :
5464 - fast_solv_9r2.c -q < top50000.sdm
9935 - zerodoku top50000.sdm -q
13661 - BB_Sudoku -t0 < top50000.sdm

Verifying uniqueness (Puzzles/second/cpu-Ghz)
4614 - fast_solv_9r2.c -q -s2 < top50000.sdm
7226 - zerodoku top50000.sdm -q -s2
10229 - BB_Sudoku -t0 -m < top50000.sdm

brit

zerothbase · Posted: Mon Nov 03, 2008 1:33 pm Post subject:

Thanks for the quick response! Not so bad for a first try.

I'm using linux in VMPlayer so my own timings are all off.

zerodoku only uses the basic naked/hidden singles logic and backtracking. I used similar code provided by dmhayden (topic - "Find hidden singles with bits" - Thanks!) for hidden singles. It also tries to find naked and hidden zeros (none available in a square or row/col/box) for backtracking purposes. And if it can't find singles, it iterates over the possibly values in the square with the least number of values possible.

For average puzzles, it appears to only be visiting 110 nodes to solve a given puzzle (averaged across thousands of puzzles). Considering that on average, the solver has to fill in ~60 values, that's fairly efficient imo. Though on the top1465, it is more like ~450 nodes - but those are designed to put a backtrack solver in a world of hurt. I tested this by simply having a counter increment every time the backtrack() function was entered and then divide by the number of puzzles.

ToDo list includes:
1) adding more logic - box/line interactions and twins/triples/quads and seeing if they improve the speed.
2) also checking for the lowest number of places a value can be in a row/col/box for iteration as opposed to only the lowest number in a square.

briturner · Posted: Mon Nov 03, 2008 2:11 pm Post subject:

I have already implemented locked candidates, naked/hidden pairs/triples/quads using bitwise operations, and I have found that for raw speed, hidden and naked singles are all you need. guessing and backtracking is a very efficient method, at least for 9x9 grids.

I suspect that as grids grow in size, logical operations will become more important then guessing and backtracking, but I could be wrong. Though it could turn out that large grids are so sparse that the DLX algorithms will be the best.

I am actually working on throwing a web page up to collect efficient ways to use bitwise operations for the different solving methodologies. It is a background task, so it could take a couple day.

brit

gsf · Posted: Mon Nov 03, 2008 4:17 pm Post subject:

briturner · Posted: Mon Nov 03, 2008 4:30 pm Post subject:

Another optimization is to not re-calculate for hidden singles if nothing in the group changed.

I have not measured the increase or decrease, but I track which groups are impacted by placing a single. If a group has not had any cells that have changed, then there is no need to look for hidden singles in that group.

I will need to test to see if not doing this check increases speed (overhead in time to maintain a list of changed groups against the time saved not searching for hidden singles). By the time you add in locked candidates and subsets, it does result in a significant savings.

brit

zerothbase · Posted: Mon Nov 03, 2008 11:44 pm Post subject:

briturner · Posted: Tue Nov 04, 2008 3:05 am Post subject:

I checked, without checking for changes in groups, the solver is around 15% slower.

well, here is what I have been using. It has been optimized based on Visual C 6.0 and on intel T5600, and contains some windows specific code. Nothing real pretty, but it works well for me.

brit

gsf · Posted: Tue Nov 04, 2008 2:56 pm Post subject:

Lunatic · Posted: Tue Nov 04, 2008 7:55 pm Post subject:

Why don't anyone uses 'in line assembly' ? I would, if Visual Basic 6 had that option.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~

briturner · Posted: Tue Nov 04, 2008 8:39 pm Post subject:

I have debated using inline assembly, and I have in the past (not for Sudoku).

Think about it, using the 128 bit SSE instructions to process 8 columns at a time, or the AMD POPCNT to check the number of bits set in 2 clock cycles.

But, then you have code that only runs on certain machines and is difficult to port or maintain.

I always believe that converting to assembly is that last thing you want to do when optimizing. I am not saying it should not be done, but it really should be the last step. Algorithms and Data Structures should always be optimized before before writing anything in assembly. Once you go to assembly, it becomes more difficult to modify and maintain.

brit

zerothbase · Posted: Tue Nov 04, 2008 11:58 pm Post subject:

I fully agree brit.

My compilers professor back in college always used to say: with how advanced modern optimizing compilers are, you'd be hard pressed to get more than 10% speed improvement from hand coded assembly over well optimized C code. But you can get large improvements going from badly coded C to well coded C (I'm paraphrasing from his thick Indian accent - but you get the idea).

I'm much more interested in elegant algorithms than I am in translating to another language to make the compiler's life easier. Much the same as I would be more interested in writing elegant poetry in my native tongue, rather than the laborious job of translating it into another language to make my reader's life easier (not to mention that the poetry loses everything that made it elegant).

Also, if you are dissatisfied with well coded C vs assembly, then you can always wait a month or two for the next CPU to be released and it will probably be 10% faster (this has been true for many years at least). Whereas if your algorithm/datastructure is horrible - it won't matter which language you use - it could take the age of the universe to solve the problem. Recursive Fibonacci is generally the classic problem in CS101 to demonstrate this.

From my testing, I've even seen the newer Java JVMs perform only about 10% to 20% slower than C (assuming you use identical algorithms and data structures). So the same might apply here to - though YMMV.

Just my thoughts.

Lunatic · Posted: Wed Nov 05, 2008 12:19 am Post subject:

I was thinking... backtracking occurs when an empty cell is encountered... an empty cell is the smallest subset short of one candidate... so there could be larger subsets short of one candidate allready present before an empty cell occurs... finding those subsets would prevent unneeded guesses and could speed up the solve speed....

Did some experiments... unfortunately, looking for those subsets took longer than the time i won by preventing those unneeded guesses.

This is how i did it:

For each house
----count unsolved cells
----if more than 1 unsolved cell
--------for any possible subset (starting with pair, then triple, and so on...)
------------count common candidates
------------if candidate count < subset then backtrack

So, i must find a better way to spot those subsets short of 1 candidate. Does anyone have any suggestion ?
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~