Saturday, June 17, 2006

Sudoku Solver

Well, I finally have finished the "brains" of the sudoku solver that I have been writing to practice python. It can solve every sudoku that it can solve, and partially fill out any that it can't. I have tested a few from Todd's "Sudoku Daily" calender. It can solve all of those, including the dreaded ~~~ ***** ~~~. It is pretty slow, the five star one took 0.56 seconds, and the one star took 0.29 seconds. This is including some display on a remote x terminal. I have been toying with the idea of writing a nice GUI for entering in the sudokus, just to learn how that stuff works. All of this was developed and run on a POS linux box running Ubuntu, its a celeron 333, 660 bogomips. The PIV 2.2 Ghz that I call my main computer gets 0.12 seconds for the five star, and 0.06 seconds for the one star (but thats with me running a bunch of stuff). So, I learned something about python. I know there is a lot of room for improvement, I coded this project so that it would be simple to understand (but hard to debug!). I deliberately traded simplicity in the program for execution time, with more information passed between the parts, it could be made much faster. I haven't looked for any mathematical algorithms for solving sudokus, and just thought about how I would approach it. Maybe I'll talk to Josh for a web based sudoku solver, using my python code as the backend. I know the demand must be extremely small, I thought of this small project back when Todd first got the calender and the whole house was doing them in their spare time. It was a small/simple project that I knew I could finish in a few hours of real work.

An interesting thing happened when I tried to run my code on my windows box, their was an error caused by python in the NTVDM CPU getting an illegal instruction. This was in the 16-bit MS-DOS Subsystem. (No, I don't have a clue what that means). This may lead to the solution of the random "Kernel_inpage_errors" that I have been having that shutdown my computer. This time, the error was because the python that I tried to run was designed to be used with cygwin, and ran perfectly there. Seems that NTVDM is a virtual machine for ms-dos and 16-bit windows programs. Windows will run NTVDM.EXE as a 32 bit application, and then the other non win-32 processes are run as children to it. ... whew. Moral of the story, use cygwin for happiness in life.

1 comment:

mike faria said...

"It is pretty slow, the five star one took 0.56 seconds, and the one star took 0.29 seconds."