The Su Doku solver as I originally hacked it out is not easy to read or understand. This is partly due to the hacked-out, uncommented, un-test-encased, generally cowboy-rigged and lacksadaisical manner of its execution, but also partly due to the idioms in which its algorithm is expressed. I knew there had to be a better way - the Monad way. And so it transpired.

The difference between this and the original code is mainly that the parts of the program that have to do with inspecting the current state of the game, determining possible future moves, and carrying them out are now bundled together in a State monad, which effectively provides a nice little execution environment for Su Doku-solving code. The Game argument, pervasive in the original code, has vanished into the fabric of the monad. The list-based approach to searching through the possible moves has been replaced by a mplus-ing together of alternative actions - if the first fails, we get to try the second instead, and so on.

Probably the biggest win is that the semantics of the solver are now a lot more explicit and uncluttered, as the generic aspects of the algorithm have been absorbed into the syntax. Getting to the stage where this was possible - e.g. setting up the Game State monad, and understanding how it threads the game’s state through bound actions without explicit arguments - was a major headache. But once I’d done that bit, I rewrote the rest pretty much in one go, and it compiled and ran with only a few minor tweaks. That’s the way it should be - the library-writer ‘s sweat is the client programmer’s gravy, if you’ll pardon the disgusting simile.

I have been greatly assisted by a couple of excellent tutorials on monads in Haskell. Monads for the Working Haskell Programmer provides both a functioning State monad and an example of its use in writing a game solver - handy, that - while All about Monads gives a very useful overview of the common uses of monadic idioms in Haskell programming.

I need to get my head round monad transformers next, so that I can write an interactive version of the solver that blends game-state and IO actions.