DLX in Python with actual pointers

DLX is the nickname of Donald Knuth’s “Algorithm X” implemented with a technique he named “Dancing Links”. This algorithm solves the so-called exact cover problem performing a depth-first search. Many famous problems and puzzles can be cast into the exact cover problem, amongst which are finding tilings (pentomino puzzles), the n-queens problem, and Sudoku. The great popularity gained by Sudoku in the last years seems to have been attracting a lot of attention to this algorithm… There are many basic implementations of Algorithm X available on the internet, including a couple in Python such as the one by Ali Assaf . This one is great, but I wanted to see a Python implementation that looked just like the original proposal, with all the crazy pointers.

(EDIT: Jeffrey Mellony has an implementation very similar to mine http://cavernum.net/dlsudoku/.)

So this is what I did in my implementation. There is a “Mode” class with pointers to four directions, just like you would declare in C, for instance. The “Matrix” class has the header node from which the rest of the matrix is grown. The __init__ method reads a list of lists that describe the lines of the matrix, with the names of the columns that are ’1′ in each line. The other methods are for covering and uncovering columns, and finally the recursive method that performs the search.

The Node class definition has four methods to iterate through the linked lists in the matrix. It should be possible to make a more elegant definition of a single general method…

So, here is the code:

## Knuth's "Algorithm X" implemented with Dancing Links, _implemented
## with actual pointers_, and all in Python.
##
## Coded by Nicolau Werneck <nwerneck@gmail.com> in 2011-05-09

class Node():
    def __init__(self):
        self.u=self
        self.d=self
        self.l=self
        self.r=self
        self.c=self

    def l_sweep(self):
        x=self.l
        while x != self:
            yield x
            x=x.l
        else:
            return

    def r_sweep(self):
        x=self.r
        while x != self:
            yield x
            x=x.r
        else:
            return

    def u_sweep(self):
        x=self.u
        while x != self:
            yield x
            x=x.u
        else:
            return

    def d_sweep(self):
        x=self.d
        while x != self:
            yield x
            x=x.d
        else:
            return

class Matrix():
    def __init__(self, column_labels, lines):
        ## The header node
        self.h = Node()
        h = self.h
        self.hdic = {}

        ## Create the colums headers
        for label in column_labels:
            ## Append new nodes to column header line, reading labels
            ## from input list.
            h.l.r = Node()
            h.l.r.l = h.l
            h.l.r.r = h
            h.l = h.l.r
            h.l.n = label
            self.hdic[label] = h.l

        ## Add lines to the matrix
        for ll in lines:
            last=[]
            for l in ll:
                q = Node()
                ## Get column header
                c = self.hdic[l]

                ## Add new node to column bottom.
                q.u = c.u
                q.d = c
                q.d.u = q
                q.u.d = q
                q.c = c

                ## Tie new node to possibly existing previous row
                ## node.
                if last:
                    q.l = last
                    q.r = last.r
                    q.l.r = q
                    q.r.l = q
                ## Current node becomes "last" node from this row.
                last=q

    ## The search algorithm. First we defoine the cover and uncover
    ## operations.
    def cover(self,c):
        c.r.l = c.l
        c.l.r = c.r
        for i in c.d_sweep():
            for j in i.r_sweep():
                j.d.u = j.u
                j.u.d = j.d                

    def uncover(self,c):
        for i in c.u_sweep():
            for j in i.l_sweep():
                j.d.u = j
                j.u.d = j
        c.r.l = c
        c.l.r = c

    ## Now the actual recursive "search" procedure. Must be called
    ## like this: m.search(0,[]). I tried to keed the code looking as
    ## much as possible like the original definition from Knuth's
    ## article.
    def search(self, k, o_all):
        if self.h.l == self.h:
            for o in o_all:
                print ''.join(self.print_o(o)),
            print
        ## Select leftmost column
        c = self.h.r
        self.cover(c)
        for r in c.d_sweep():
            o_k = r
            for j in r.r_sweep():
                self.cover(j.c)
            self.search(k+1, o_all+[o_k])
            ## Dunno why Knuth put this line in his code, not
            ## necessary. Maybe a premature optimization in mind?
            #r,c = o_k,r.c 
            for j in r.l_sweep():
                self.uncover(j.c)
        self.uncover(c)

    ## To print the solution(s)
    def print_o(self, r):
        out = [r.c.n]
        for x in r.r_sweep():
            out.append(x.c.n)
        return out

##
## Run the damn thing
if __name__ == '__main__':
    cols=['a','b','c','d']
    lines=[['a'],['b'],['c'],['d'],
        ['a','b'],['a','c'],['a','d'],['b','c'],
        ['b','d'],['c','d'],['a','b','c'],['a','b','d'],
        ['a','c','d'],['b','c','d'],['a','b','c','d'],]

    m = Matrix (cols, lines)
    #m.print_matrix()
    m.search(0, [])

And this is the output:

$ python dlx.py
a b c d
a b cd
a bc d
a bd c
a bcd
ab c d
ab cd
ac b d
ac bd
ad b c
ad bc
abc d
abd c
acd b
abcd

I am not much sure how bad this implementation is regarding speed and memory, but I have one possible modification in mind already: just using a numpy array instead of the node objects. Each line is a node, and each column of the array represents one of the values, u, d, l, r, c.

The code is also available at pastebin,
http://pastebin.com/DWA1RMfG. Have fun!…