Greater-than Sudoku is like an ordinary Sudoku puzzle, but the number clues are replaced with less-than and greater-than relations.

Sergii Dymchenko showed how to solve it with ECLiPSe, and Hakan Kjellerstrand translated that to Picat, so I couldn’t resist trying to model it in MiniZinc.

(read more)

An application I’m writing requires a lot of linear interpolation of a function. There’s so much of it, in fact, that it was the biggest single contributor to the running time. In this article I show how I used Template Haskell to make it much faster and cut the overall running time of the application by about a third.

(read more)

Diagrams is the best library for drawing diagrams in Haskell. But can it be used as part of a user interface so you can interact with parts of a diagram?

The answer is: yes.

(read more)

Recently I was surprised by the behaviour of a Haskell program I wrote. This simple example demonstrates the problem:

-- Simple.hs
import System.Environment
main = do
  n <- fmap (read . head) getArgs
  print (length (sequence (replicate n "abc")))

This computes the length of the list formed by every n-sized combination of the letters “a”, “b” and “c”. For example, if n is 4, the first few elements of the list are “aaaa”, “aaab”, “aaac”, “aaba”. (In other words, it’s a slow way to compute 3 to the power of n.) I expected this program to take near-constant space, even though the list might be very long, because it can be consumed by length as it is produced by sequence.

However, as n increases the space required grows exponentially.

(read more)
Diagrams internals

This article covers a small part of the internals of Diagrams, a Haskell library for drawing static and animated diagrams. In particular, I give an overview of how a diagram is represented, how paths work, and how attributes are applied to diagrams. The Diagrams library has a lot in it, so not everything can be covered in great detail in such a short article.

Understanding the internals of Diagrams is not necessary for using it effectively – you can make complex diagrams without knowing any of how it works. You might be interested in the internals if you want to extend the library, or add a new rendering backend, or just fix a bug or add documentation. This material might also be of interest to people who want to see examples of type classes, existential types and heterogeneous lists.

(read more)

The schedule for the International Workshop on Modelling and Reformulation for Constraint Programming is now available.

The submission deadline for the International Workshop on Modelling and Reformulation for Constraint Programming has been extended to 16 July 2012.

Get more information here.

The game Minesweeper is a fun diversion, but even more fun would be to get the computer to solve it for us. I’ve written a basic solver for the version of Minesweeper from Simon Tatham’s excellent Portable Puzzle Collection, called Mines. My solver interacts with the game just like a human player would: by reading the screen’s contents and moving and clicking the mouse.

Here is a video of the solver in action.

(read more)
ModRef 2012

The International Workshop on Modelling and Reformulation for Constraint Programming is on again! The submission deadline is 13 July 2012.

Get more information here.

A few months ago, Laurent Vaucher wrote a couple of articles (starting with this one) about solving the puzzle game Hexiom using search algorithms and hand-crafted constraint propagation. It looked like an interesting puzzle, and I was curious about how well a generic constraint solver would perform and how to model the problem. Here I describe how I used MiniZinc and Gecode to tackle it.

(read more)