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.
In order to understand the total idea, you have to refer Knuth's paper here.
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