backtrack by doubly-link

Dancing Link

A. First Edition

This is a program to implement the so-called "dancing link" which is introduced in Knuth's paper. This is really a super

acrobatic and I am sure that not many programmers can understand the algorithms.

B.The problem

The exact cover problem:

{0,0,1,0,1,1,0},
{1,0,0,1,0,0,1},
{0,1,1,0,0,1,0},
{1,0,0,1,0,0,0},
{0,1,0,0,0,0,1},
{0,0,0,1,1,0,1}

As for the above matrix, can you find a subset of rows such that each column has exactly one 1. Can you find such a subset

of rows? This is a typical NP-complete problem.

C.The idea of program

In order to understand the total idea, you have to refer Knuth's paper here.

D.The major functions

I lost patience of explaining the complicated algorithms because I don't understand it quite well myself.

E.Further improvement

F.File listing

1. dancingLink.cpp

　

file name: dancingLink.cpp

#include <iostream>

using namespace std;

enum Direction
{
    Left, Right, Up, Down
};

const int RowNumber=6;
const int ColNumber=7;
const int MaxNameLength=32;
const int MaxDataLength=32;
const int MaxBackTrackDepth=RowNumber;

struct Node
{
    Node* L;
    Node* R;
    Node* U;
    Node* D;
    Node* C;
    char* data;
    int size;
    char* name;
    void display()
    {
        if (name!=NULL)
        {
            cout<<"name="<<name<<"\n";
        }
        if (data!=NULL)
        {
            cout<<"data="<<data<<"\n";
        }
        if (size!=-1)
        {
            cout<<"size="<<size<<"\n";
        }
    }
};

Node* stack[MaxBackTrackDepth];

int matrix[RowNumber][ColNumber]=
{
    {0,0,1,0,1,1,0},
    {1,0,0,1,0,0,1},
    {0,1,1,0,0,1,0},
    {1,0,0,1,0,0,0},
    {0,1,0,0,0,0,1},
    {0,0,0,1,1,0,1}
};

Node* nodeStep(Node* node, Direction dir, int step);
void rightInsert(Node* theLeft, Node* theNode);
void downInsert(Node* theUpper, Node* theNode);
void horizonRemove(Node* node);
void verticalRemove(Node* node);
Node* createNode();
void display(Node* head);
Node* initialize(int** matrix);
Node* createHeader(int colNumber);
//I prefer to make the pointer null which is safe
void uninitialize(Node*& head);

void printSolution(int depth);
void search(Node* head, int depth);

Node* initialize(int matrix[][ColNumber])
{
    Node* result=createHeader(ColNumber);
    Node* start=result->R;
    Node* upper, *left, *node, *currentHeader;

    for (int r=0; r<RowNumber; r++)
    {
        left=NULL;
        for (int c=0; c<ColNumber; c++)
        {
            if (matrix[r][c]>0)
            {
                //create a new node
                //when the node is created, it is self-circule
                //which means it loop both l,r,u,d by itself,
                //so it is safe to just insert either horizontal or verticle
                node=createNode();
                node->data=new char[MaxDataLength];
                sprintf(node->data, "data row[%d],col[%d]", r, c);

                //get current header node
                currentHeader=nodeStep(start, Right, c);
                if (currentHeader->size==0)
                {
                    upper=currentHeader;
                }
                else
                {
                    //move downwards to the current upper of inserted node
                    upper=nodeStep(currentHeader, Down, currentHeader->size);
                }

                //insert node and update header
                downInsert(upper, node);
                node->C=currentHeader;
                currentHeader->size++;

                //possible to insert into row link
                if (left!=NULL)
                {
                    rightInsert(left, node);
                }
                //this is done always
                left=node;
            }
        }
    }
    return result;
}

Node* nodeByDirection(Node* node, Direction dir)
{
    Node* result=NULL;
    switch (dir)
    {
    case Left:
        result= node->L;
        break;
    case Right:
        result= node->R;
        break;
    case Down:
        result=node->D;
        break;
    case Up:
        result=node->U;
        break;
    }
    return result;
}

void doDisplay(Node* node, Direction dir)
{
    Node* ptr=node;
    while (true)
    {
        ptr=nodeByDirection(ptr, dir);
        if (ptr==node)
        {
            break;
        }
        ptr->display();
    }
}

void display(Node* head)
{
    Node* node=head->R;
    //cout<<"now display header rows\n";
    //doDisplay(head, Right);
    cout<<"************************now display column by column**********************\n";
    while (node!=head)
    {
        //node=nodeStep(head, Right, i);
        cout<<">>>now display column<<<\n";
        node->display();
        doDisplay(node, Down);
        node=node->R;
    }
}

Node* createHeader(int colNumber)
{
    Node* result=createNode();
    Node* current=result;
    Node* node;
    result->name=new char[MaxNameLength];
    sprintf(result->name, "head node with %d column", colNumber);
    for (int c=0; c<colNumber; c++)
    {
        node=createNode();
        node->size=0;
        node->name=new char[MaxNameLength];
        sprintf(node->name, "column %d header", c);
        rightInsert(current, node);
        current=node;
    }
    return result;
}

Node* nodeStep(Node* node, Direction dir, int step)
{
    Node* result=node;
    for (int i=0; i<step; i++)
    {
        result=nodeByDirection(result, dir);
    }
    return result;
}

Node* createNode()
{
    Node* result;
    result=new Node;
    result->L=result;
    result->R=result;
    result->U=result;
    result->D=result;
    result->C=result;
    result->data=NULL;
    result->size=-1;
    result->name=NULL;
    return result;
}

Node* createNode(char* theData)
{
    Node* result=createNode();
    result->data=new char[MaxDataLength];
    strcpy(result->data, theData);
    return result;
}

void horizonInsert(Node* node)
{
    Node* left=node->L;
    Node* right=node->R;
    left->R=node;
    right->L=node;
}

void verticalInsert(Node* node)
{
    Node* upper=node->U;
    Node* lower=node->D;
    upper->D=node;
    lower->U=node;
}

void horizonRemove(Node* node)
{
    Node* left=node->L;
    Node* right=node->R;
    left->R=right;
    right->L=left;
}

void verticalRemove(Node* node)
{
    Node* upper=node->U;
    Node* lower=node->D;
    upper->D=lower;
    lower->U=upper;
}

//these kind of operation was written to be as simple as possible
//so that even a fool can understand what is going on
void rightInsert(Node* theLeft, Node* theNode)
{
    //using temp variable is safer, and you don't have to worry about the
    //the order of operation
    Node* theRight=theLeft->R;
    theNode->L=theLeft;
    theNode->R=theRight;
    theLeft->R=theNode;//danger! if you don't use temp variable
    theRight->L=theNode;
}

//these kind of operation was written to be as simple as possible
//so that even a fool can understand what is going on
void downInsert(Node* theUpper, Node* theNode)
{
    Node* theLower=theUpper->D;
    theNode->U=theUpper;
    theNode->D=theLower;
    theUpper->D=theNode;//this order is only true when temp variable is used
    theLower->U=theNode;
}

void deleteNode(Node* node)
{
    if (node->data!=NULL)
    {
        delete node->data;
    }
    if (node->name!=NULL)
    {
        delete node->name;
    }
    delete node;
}

//I prefer to make the pointer null which is safe
void uninitialize(Node*& head)
{
    Node* right;
    Node* lower;

    right=head->R;

    while (right!=head)
    {
        //now we start to delete this column
        lower=right->D;
        while (right!=lower)
        {
            //unlink
            verticalRemove(lower);
            //delete
            deleteNode(lower);
            //point to next
            lower=right->D;
        }
        //now we remove header and delete it
        //unlink
        horizonRemove(right);
        //delete
        deleteNode(right);
        //point to next
        right=head->R;
    }
    //need to delete head
    deleteNode(head);
    head=NULL;
}

Node* nextColumn(Node* head)
{
    return head->R;
}

void coverColumn(Node* colHeader)
{
    Node* lower;
    Node* right;
    //first remove the column header
    horizonRemove(colHeader);
    lower=colHeader->D;
    while (lower!=colHeader)
    {
        right=lower->R;
        //but we don't unlink ourselves
        while (right!=lower)
        {
            //unlink data from its column
            verticalRemove(right);
            //reduce size of that column
            right->C->size--;
            //go right for next available column
            right=right->R;
        }
        //go down for next available row
        lower=lower->D;
    }
}

void uncoverColumn(Node* colHeader)
{
    Node* upper;
    Node* left;
    upper=colHeader->U;
    while (upper!=colHeader)
    {
        left=upper->L;
        while (left!=upper)
        {
            verticalInsert(left);
            //update the size of column i
            left->C->size++;
            left=left->L;
        }
        upper=upper->U;
    }
    horizonInsert(colHeader);
}

void printSolution(int depth)
{
    Node* ptr;
    cout<<"one solution is found\n";
    for (int i=0; i<depth; i++)
    {
        ptr=stack[i];
        do
        {
            cout<<ptr->C->name<<"\t";
            ptr=ptr->R;
        }
        while (ptr!=stack[i]);
        cout<<"\n";

    }
}

void search(Node* head, int depth)
{
    Node* columnHeader;
    Node* row;
    Node* ptr;

    if (head==head->R)
    {
        printSolution(depth);
        return;
    }
    columnHeader=nextColumn(head);

    //cout<<"********before cover column \n";
    //columnHeader->display();
    //display(head);
    coverColumn(columnHeader);
    //cout<<"********after cover column \n";
    //columnHeader->display();
    //display(head);

    row=columnHeader->D;

    while (row!=columnHeader)
    {
        //first we need to leave a trace for us to back track in this
        //stack-like array for data we searched
        stack[depth]=row;
        //traverse all column in this row
        ptr=row->R;
        while (row!=ptr)
        {
            //cout<<"********before cover column \n";
            //ptr->C->display();
            //display(head);
            coverColumn(ptr->C);
            //cout<<"********after cover column \n";
            //ptr->C->display();
            //display(head);

            ptr=ptr->R;
        }
        search(head, depth+1);
        //backtrack
        row=stack[depth];
        columnHeader=row->C;
        ptr=row->L;
        while (row!=ptr)
        {
            uncoverColumn(ptr->C);
            ptr=ptr->L;
        }
        row=row->D;
    }
    uncoverColumn(columnHeader);
}

int main()
{
    Node* head;
    head=initialize(matrix);
    display(head);

    cout<<"\nnow let's search:\n";
    search(head, 0);
    uninitialize(head);


    return 0;
}

//these kind of operation was written to be as simple as possible
//so that even a fool can understand what is going on
void upInsert(Node* theLower, Node* theNode)
{
    Node* theUpper=theLower->U;
    theNode->U=theUpper;
    theNode->D=theLower;
    theUpper->D=theNode;
    theLower->U=theNode;
}

//these kind of operation was written to be as simple as possible
//so that even a fool can understand what is going on
void leftInsert(Node* theRight, Node* theNode)
{
    Node* theLeft=theRight->L;
    theNode->L=theLeft;
    theNode->R=theRight;
    theLeft->R=theNode;
    theRight->L=theNode;
}

　

A snapshot of running automated testing:

************************now display column by column**********************
>>>now display column<<<
name=column 0 header
size=2
data=data row[1],col[0]
data=data row[3],col[0]
>>>now display column<<<
name=column 1 header
size=2
data=data row[2],col[1]
data=data row[4],col[1]
>>>now display column<<<
name=column 2 header
size=2
data=data row[0],col[2]
data=data row[2],col[2]
>>>now display column<<<
name=column 3 header
size=3
data=data row[1],col[3]
data=data row[3],col[3]
data=data row[5],col[3]
>>>now display column<<<
name=column 4 header
size=2
data=data row[0],col[4]
data=data row[5],col[4]
>>>now display column<<<
name=column 5 header
size=2
data=data row[0],col[5]
data=data row[2],col[5]
>>>now display column<<<
name=column 6 header
size=3
data=data row[1],col[6]
data=data row[4],col[6]
data=data row[5],col[6]

now let's search:
one solution is found
column 0 header column 3 header
column 1 header column 6 header
column 2 header column 4 header column 5 header
Press any key to continue