I recently had the need to check a couple of puzzles that were geared towards intuitive solving, and consequently tricky to prove correct by hand. Luckily enough, Nikolai Beluhov posted an excellent Curve Data solver at just the right moment, allowing me to fix one broken puzzle. For the other, I took the chance to finally play around with logic programming. Prolog is likely the best-known language from this domain, but I went with Mercury, which is quite close to Prolog, but adds a couple of nice things like a static type system.

The project was quite successful: It solved the problem and was a lot of fun. Unfortunately, the solver turned out a little too complex to fit into a blog post, largely due to the complexity of the puzzle type. Thus, I decided to break it down to a way simpler (simplistic, even) puzzle, with the option of presenting the full solver in a second post.

Here’s the puzzle: Write the word “PUZZLE” in the grid by placing letters in some empty cells. The word may read in any of the eight horizontal, vertical or diagonal directions.

Below, we’ll develop the solver step by step.
Continue reading →