1.cpp

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

#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