Since my last post involving a GNU Octave (MatLab) algorithm for solving sudoku puzzles I have successfully ported my code into C++. I must say the porting of functional code from GNU Octave to C++ was a royal pain in the ass. In fact I think that I would have been much further ahead of the game if I would have just started from scratch with the development of the C++ code.
The good news is that I now have an exceptionally fast and robust stand alone program that has solved EVERY sudoku that I have thrown at it. The easiest puzzle completed the solution in less than one-half of a blazing millisecond. (0.00045 s) The normally “hardest” puzzles found in magazines and newspapers are usually solved in less than fifteen-thousandths of a second (0.015 s) I’m pretty stinking happy with that! The supposed “hardest” sudoku in the world” is easily solved in about five seconds and, on average, runs about twenty-four thousand (24,000) loops to complete.
If you remember the GNU Octave version would usually find a solution, on average, in about three thousand (3000) loops. The reason for this is the random number generator used in the C++ libraries are not at all that random, in fact they call them “pseudo” random generators. They start out picking similar value patterns (read not very randomly) early on and only after a while do they diverge. TWO thumbs up to both GNU Octave and MatLab for their robust, and truly random number generators.
*************** update 20:09 CST (local) *******************
Another very interesting update. I decided to use Apple’s Xcode to compile and run the program on my Mac Book Pro and was very pleasantly surprised. Normally Xcode uses Objective C as its native programming language for all Apple products. I was happy to find out that Apple also has very good support for C++ and also has access to superb libraries. After recompiling in Xcode, the executable was able to solve the “Hardest Sudoku in the World” in an average time of 0.7526 seconds and with an average 3636 of main loops to finish. I’d have to say that Apple’s Xcode random number generator is, thus far, the best I’ve seen. It’s also a very good IDE to boot!
Here is the updated executable Mac Xcode compiled program that also has the option of specifying the input file after clicking on in it directly from the finder window: Sudoku_Solver
Below are the executable binary files (programs) along with several input files
as well as the source code for your enjoyment. The program will run on the command line by itself without any arguments, in this case a default puzzle is loaded. One difference from the GNU Octave input files is that there needs to be a blank line at the top of the CSV input file due to the behavior of the C++ infile library subroutines. Otherwise the exact name of the input file should follow the program name, separated by a space, example:
There are executables for Mac, Linux, and Windows. The Windoze version was compiled with an old version of Microsofts Visual C++ 6.0 compiler and requires an input file to be specified or the program will crash. (typical for Microsoft not to adhere to any industry standards) The other two were compiled with current versions of gcc (g++).
(see updated link below)
I Updated files to allow double clicking from within Finder or Explorer.
Mac users may have to enter path to puzzle files along with the puzzle file name, only if starting by double clicking icon. (This is because the Terminal assumes the file is located in the users Home directory) ex: Documents/sudoku/HardestOne.csv
Linux users will probably need to make sh script if wishing to double click on an icon using Natilus.
Windows version newly recompiled using MinGW gcc and thus no longer crashes in XP due to Microsoft’s Visual C++ compiler.