« Slashdot Book Review Effect -- Visual Illustration | Main | Backing up PC data to a Linux box with rsync »

Sudoku Solving Program : Translating Python to JavaScript

I had thought of writing a Sudoku solving program while in India last year, but then my laptop died on a sudden surge of voltage (not uncommon in India) and I had to shelf the idea. Once back to US, I never found enough time to code the solution and the whole thing just faded away from my memory.

So when I came across Peter Norvig's Python program to solve every Sudoku last week, I took the time to understand the underlying data-structure and the algorithm and couldn't help but appreciate the beauty of the solution (and Python code). I even downloaded the code and tried it out on a couple of puzzles. It worked fast and without any flaw, but with a minor annoyance -- the program must be run as a command line tool and the input must be entered as a string of 81 characters. Not a problem for me, but perhaps not very "user friendly" to most people on the Internet.

So I decided to rewrite the program in JavaScript, the most ubiquitous language on the Web, with a pretty GUI and make it available as a Web based program to solve Sudoku Puzzles. In this program you can either enter a puzzle on a 9x9 grid in a WYSIWYG manner or just pick one from 95 hard puzzles as a starting point and then click on "Solve" button to get a solution.

One thing I noticed is that the JavaScript version is not particularly fast. Some of the puzzles take long enough (more than a couple of seconds, even on 2+ GHz machines) that the Browser may prompt you to abort (or Continue, you should click on "continue"). The original Python code solves the same puzzle on the same machine much faster, sometime by a factor of 10. This could be due to the fact that I did a literal translation of Python constructs to JavaScript and haven't paid any attention to reduce hash look-ups or any other optimization. This could also be due to slow JavaScript interpreters (I tried FireFox1.5+ and IE7.0).

Another significant observation I have is about the relative compactness and homogeneity of Python code. Python treats iteration over strings, lists, dicts, and sets uniformly and in a very natural fashion. The corresponding JavaScript code lacks this elegance. You should compare the Python code with the JavaScript Code to get an idea of what I am talking about.

PS: I came across this super compact Perl script to solve Sudoku puzzles while researching for this post, after I had already written the JavaScript code. This code employs a simpler data-structure and strategy to to eliminate values and find the right solution to keep the code size to a minimum, but perhaps is not as efficient. It would be interesting to see if this code can be modified to incorporate the elimination and search improvements of the former.

Post a comment

(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)

About

This page contains a single entry from the blog posted on March 12, 2007 9:39 PM.

The previous post in this blog was Slashdot Book Review Effect -- Visual Illustration.

The next post in this blog is Backing up PC data to a Linux box with rsync.

Many more can be found on the main index page or by looking through the archives.

Powered by
Movable Type 3.33