Sunday, August 5, 2012


Faster than AT&T Sudocoup - 326x Faster!

Glenn Fowler of AT&T Labs wrote an excellent Sudoku application - Sudocoup - which I have envied for some time.  As I developed my own Sudoku solver, I compared its execution time for various puzzles to that of Sudocoup.

In April, Sudocoup could solve 9x9 puzzles that mine could not.  By June, my solver could do any puzzle up to 36x36 - but far slower than Sudocoup.  In July, I implemented a raft of additional constraint logic reduction routines that allowed solving 64x64 puzzles in a few minutes - as compared to the seconds required by Sudocoup.  144x144 remained completely out of reach.

However, I finished implementing single-node chain reduction for my solver, which I named Arcterik Sudoku.  Arcterik Sudoku solves this 256x256 puzzle in 0.635 seconds, whereas  Sudocoup requires 3 minutes, 26 seconds.

So, I've hit the faster than Sudocoup milestone that seemed unreachable for so long.  My ultimate goal for this project, aside from sharpening my graph theory and learning some new things, is to handle 65536x65536 puzzles in reasonable time.

16x16 in the titlebar refers to block size - 16*16=256, the width of the puzzle


Post a Comment

Subscribe to Post Comments [Atom]

<< Home


July 2009   August 2009   September 2009   October 2009   November 2009   December 2009   January 2010   September 2010   December 2010   January 2011   February 2011   April 2011   June 2011   August 2011   February 2012   June 2012   July 2012   August 2012   October 2012   November 2012   January 2014   April 2014   June 2014   August 2014   September 2014   October 2014   January 2015   March 2015   April 2015   June 2015   November 2015   December 2015   January 2016   June 2016   August 2016   January 2017   March 2017   April 2018  

This page is powered by Blogger. Isn't yours?

Subscribe to Posts [Atom]