• Recent Articles
• By Topic
• By Year
• About me

Sudoku Solver

14.08.2013 Permalink

I'm not a Sudoku player. And even worse: before I went on my vacation last week, I didn't even know the exact rules. With me, my wife and my daughter my father-in-law Jürgen travelled with us. We had a nice flat on a farm and enough time in the evenings, so Jürgen told me that he likes to solve Sudokus. I suspected that Sudoku is one of those solitaire games that could easily be solved by a deterministic algorithm, which is the reason why I don't like playing these games. After all, it's at the root of my profession to not do anything time-consuming using my hand or my brain that a computer can do. Unless it's fun, of course.

So I asked him about the rules and how he approaches the solution. And as we talked and had another glass of wine I thought about how an implementation of a Sudoku solver would look like in Clojure. It seemed not to be too much work... no, it seemed more like fun.

Three evenings later I finally finished a solver, you can find it as Github repo.

In the code you can spot some interesting idioms that I consider very typical for Clojure programs, and which contrast well how the FP approach differs from an imperative OO approach:

Concepts backed by ordinary data structures

To write a clean implementation I needed some concepts: a cell with all its candidate values, a fact denoting a cell that has a definite value, a region as abstract term for all 9 cells of a row, a column or a 3x3 block, a board comprised of 81 cells and so on. In an OOP world I'd have created some classes and then had to decide where to locate corresponding operations. And answer questions like "Is a board a region, just a little bit bigger?" or "Is a fact a cell with a special property?" to get inheritance and method reuse right.

In Clojure I still need concepts but I don't need specialised types to express concepts. To make them a little more formal, factory functions suffice that give the reader a clue what makes up a cell, a fact or a board. In addition to conciseness this earns me the accessibility to all those nice collection processing functions that work on Clojure sequences.

Collection processing dominates

The intuitive way to represent a Sudoku board is a nested array that models two dimensions. If Clojure did not have such a rich toolbox for querying and transforming sequences the intuitive approach would be fine. But, to take full advantage of what Clojure offers a board is best represented as a sequence of maps, where each map represents a cell. And hey, a region has the same representation, as well as facts or possible guesses that can be derived from a board. That leads to great uniformity and -as a nice consequence - to interoperability of almost all functions.

In OOP the question of data representation is an encapsulated implementation detail of a class. That looks like a nice idea first, but forces you to implement similar collection processing functionality over and over again. More code, more bugs, bad idea.

Predicates and queries

The core of the algorithm is a small set of transformation functions. To enable a comprehensible implementation of these I created several short functions that query cells or a board. They create a conceptual layer that allows me to express the algorithm very clearly on a higher level of abstraction. This is exactly one of the central promises of OOP, and you can do the same in an OO language. In OO the only caveat is that you must decide in which type to place these helpers, and sometimes this question is hard to answer without doubt. It's getting even harder when you need implementation reuse because OOP only offers inheritance or delegation.

Conclusion

Yes, I can detect some recurring best practices across the few libraries I wrote until now:

On top of collection processing and simple data structures I find it helpful to describe concepts up-front. A concept defines a name and associates it with a data structure, invariants and rules. Alternatively a concept could also be a specific kind of function (see for example Rings handler or middleware) or even a protocol. A concept is only loosely coupled to its implementation. Instances could occur everywhere without referring to the initial code that introduced the concept first. A concept is open, whereas an OO class or interface is somewhat closed. Of course you can extend types in OOP but you need further complexity like inheritance, factories, extensions, decorators or other OO pattern stuff.

A safe way to create instances of a concept is a factory function. I quickly introduce those functions and prefix their names often with verbs like "make-" or "create-". If I omit prefixes instead, then I sometimes need to cripple local symbol names to avoid name clashes or unwanted shadowing.

If I have a concept and its data structure then I often need additional query functionality to enable other functions to work on a higher level of abstraction with my concepts. Among those, predicates (functions that return true/false) play an important role because some collection comprehensions like filter or remove expect a predicate as parameter. Beside that most conditional expressions really benefit from well-named predicates.

When I create functions that I expect to interoperate with each other I always keep in mind how these functions can support the threading macros -> and ->> as well as some higher-order functions like partial. Especially parameter order plays a much more important role to support interoperability than in OOP.

After all: it was fun. And I really enjoy that after experimenting with Clojure and FP now for a year, I feel like I'm gaining some sense for idiomatic style that I can put into words and share with others.