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