**By** Carl Mäsak (masak)

**Date:** Saturday, 12 November 2011 10:20

**Duration:** 40 minutes

**Language:** English

**Tags:** algorithms languages problems solutions 蝶

Donald Knuth's "Dancing Links" algorithm deserves wider recognition. It can solve the N-queens problem. It can help us tile pentominoes. It makes solving a Sudoku problem trivial.

There's only one little issue: these problems are all solved in another domain which we can call the "big huge matrix of ones and zeroes domain". Constructing such a matrix manually is about as fun as boning fish.

Solution: I wrote a set of parsers that can understand a given problem type, so that we can always deal with cute ASCII representations of the problems, and never the matrix itself. We become unfettered from the technical specifics of the algorithm, while still reaping all the benefits from it.

The same idea was implemented in Perl 5/Moose (for prototyping), C (for speed), and Perl 6 (for beauty), and I will say a thing or two about what's nice about implementing a small project like this in each of those languages.

**Attended by:**

- Nicholas Clark
- Jody Belka (knewt)
- Adam Bartosik
- Tomas Doran (t0m)
- Mike Cartmell
- Victor Churchill
- Tielman de Villiers
- Neil Hemingway (neilh)
- Rafiq Gemmail (Raf)
- Peter Rabbitson (ribasushi)
- Arthur Schmidt (fREW)
- Paul Evans (LeoNerd)
- Martin Evans (mjevans)
- Alex Burzyński
- Dongxu Ma (dx)
- Rikki Guy
- Kayvan Javid