As an exercise, I translated Peter Norvig’s Sudoku solver from Python to Clojure. There have been a couple other attempts before, but they both leaned on Clojure’s reference types as a mutability-crutch. This implementation uses only immutable data structures.
To facilitate side-by-side comparison, I tried to retain the algorithm and basic code structure of Dr. Norvig’s implementation: variables, functions, and sections are named the same, etc. Some of the functions could be broken up into smaller pieces, but they’re not sinfully long.
What I didn’t do was focus on performance – beyond choosing what I thought were appropriate data structures up front. I wanted to bang it out using the tools that Clojure puts within close reach, and not worry about bleeding-edge speed.
On the surface, the two versions are comparable in length and expressiveness. They both make extensive use of list comprehensions and their language’s particular idioms to help make things concise.
The algorithm remained intact for the most part. Dr. Norvig’s code didn’t rely too much on side effects so it wasn’t terribly difficult.
To avoid mutation, the Clojure version relies heavily on
reduce to build a succession of game states. One challenge was that vanilla
reduce wasn’t a perfect fit: the algorithms in
eliminate need to short circuit if a contradiction is encountered, which in turn allows the game-tree search to move on to better prospects. I resorted to creating
reduce-true, which acts like regular
reduce except that it stops feeding in values if any intermediate reductions produce a logically false value (which
eliminate does when a contradiction is detected). Other alternatives crossed my mind (monads!?) but this seemed the most natural.
random-puzzle functions were the trickiest to translate. I’ve been practicing translating imperative algorithms into functional style a lot lately, and it’s getting easier. Thinking functionally forces you to become acutely aware of the values at play in your code — how and when one value gives rise to another, and what other values it depends on to do so.
The Clojure version didn’t have to worry about copying (see the
search function), since everything is immutable. Immutability makes doing backtracking-style searches easy: no need to “undo” changes, since you never changed anything in the first place!
A bit to my surprise, the Python version is faster. This may be due to the choice of data structures: I chose to use vectors and sets to represent the Sudoku squares and digits, whereas the Python version uses strings, which are relatively lightweight. Changing it now would be too much work, but if anyone is curious enough to make the effort, speak up.
Just for kicks, I made a token attempt at parallelizing the algorithm by using
search‘s first run (spawning between 2 and 4 threads usually). That didn’t help, probably because it causes extraneous work to be done when the solution is usually within close range in the game tree.
There are surely faster methods and algorithms possible. Again, my main goal was to practice thinking functionally, and compare the expressiveness of the resulting code to Python’s clean style. I think the Clojure code compares favorably in this light.
Solved 50 of 50 easy puzzles (avg 0.01 secs (101 Hz), max 0.02 secs). Solved 95 of 95 hard puzzles (avg 0.03 secs (33 Hz), max 0.16 secs). Solved 11 of 11 hardest puzzles (avg 0.02 secs (64 Hz), max 0.04 secs). Solved 99 of 99 random puzzles (avg 0.01 secs (97 Hz), max 0.02 secs).
Solved 50 of 50 easy puzzles (avg 0.01 secs (126 Hz), max 0.01 secs). Solved 95 of 95 hard puzzles (avg 0.03 secs (34 Hz), max 0.13 secs). Solved 11 of 11 hardest puzzles (avg 0.01 secs (93 Hz), max 0.02 secs). Solved 99 of 99 random puzzles (avg 0.01 secs (118 Hz), max 0.01 secs).
(The unpredictable spikes mentioned by Dr. Norvig persist in the Clojure version. Every once and a while,
random-puzzle generates a puzzle that takes a very long time to solve. I didn’t make any effort to correct the problem.)