dancing-links

This is the dancing-links project dev-server. As well as something you can run yourself, you can also access it on heroku.

Background

This project implements algorithm X (as described by Donald Knuth) in javascript using the dancing links data structure. Knuth's paper is readable and interesting (with diagrams that definitely help). The intention is that this code be documented, readable, tested, and that it can work on node.js, in the browser or in Rhino.

Exact Cover Problem

The Exact Cover Problem is an optimisation problem. Given a set of constraints that must be satisfied and a set of choices, each of which satisfies one or more of the constraints, you need to select a subset of the possible choices that ensures that every constraint is satisfied once and only once.

Here's my favourite explanation:

Lets say, you're doing your exam for your piano grade. Lets think of the columns not as columns, but as a precise list of tricks you must show to the examiner that you are able to do before he/she can give you the pass. The examiner is also very easily bored, and will immediately fail you if you do the same trick twice. Now, think of the rows not as rows, but as an exact song list you can choose from to play to the examiner. You may choose one or more songs from your list of songs. You can choose to play all the songs in your list. Songs can show the examiner different tricks, so she/he can mark you off for them. You must pick a set of songs such that every trick on the examiner's list is fufilled exactly once.

-- Xi Chen

As it turns out, a number of well known problems can be represented as Exact Cover problems, such as Sudoku, Pentonimos, N-Queens.

Getting Started

Check the code out with git from the github repository: git://github.com/kybernetikos/dancing-links.git

You can also access it on cloud9.

Ideally you would have node.js installed, in which case you can run the tests by using

npm test

inside the project, or you can run them with build\runtests.cmd (I have been developing in eclipse on windows).

You can run the devserver after getting the dependencies with

npm install 
npm start

Which will start up a web server that serves the bundled js file containing all the code so you can access the files from the browser. It will also automatically rebuild and serve the jsdoc too.

If you don't have node, within eclipse you can use 'debug as rhino' on the rhino-index.js file to see some sudoku solved (very slow - node is much faster).

The Code

Algorithm X works by searching all the possibilities, back-tracking as soon as it finds that a certain option isn't working. See Knuth's paper for more details.

Dancing links is a particular way of implementing algorithm X that turns out to perform well in many cases.

Picture the problem as being written out in table form. Each column represents a Constraint, something that must be satisfied exactly once in any solution. For Sudoku, an example constraint is 'there must be a 1 in the first row'. For Polyonimos an example constraint is 'the square piece must be placed somewhere on the board'. In the example above, the piano techniques are the Constraints. The rows represent Choices that you can make. In the above example, these are the piano pieces that you select from. In Sudoku, a choice might be 'write 3 in the first cell of the first column'. In polyonimos, a choice might be 'place the square piece so it's top left corner is at 0,0'.

Typically, there will be many hundreds of rows and columns to adequately capture a problem.

Dancing links is a technique to make it very quick to remove things from this table and then add them again if it didn't work out.

The code has a generic dancing links implementation called Network, and extra code that uses that Network to solve specific puzzles, like Sudoku or Polyonimos.

Sudoku

Sudoku can be represented as an exact cover problem. There is a constraint for each number in each row, column and area. (i.e. a constraint that there be a 1 in row 1 (and likewise for each row, column and area), a constraint that there be a 2 in row 1 (and likewise for each row, column and area).

The choices are for each cell, a number being written into it. So one choice might be '1 in cell 1', another might be '2 in cell 1'.

Try it here:


			
			
		

Polyonimos

Polyonimos can also be represented as an exact cover problem. There are two kinds of constraints, cell constriants, which represent the fact that every cell must be covered, and shape constraints, which represent the fact that every shape must be used.

There is a choice for every place that each shape can be placed.