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.

　

The N-Queen problem:

It should be known to every student of computer science.

　

　

　

C.The idea of program

　

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.h

2. dancingLink.cpp

3. queen.h

4. queen.cpp

5. main.cpp

file name: dancingLink.h

#include <iostream>
using namespace std;

const int MaxNameLength=32;
const int MaxDataLength=32;

struct Node
{
	Node* L;
	Node* R;
	Node* U;
	Node* D;
	Node* C;
	char* data;
	int size;
	int row;
	int col;
	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";
		}
		if (row!=-1)
		{
			cout<<"row="<<row<<"\n";
		}
		if (col!=-1)
		{
			cout<<"col="<<col<<"\n";
		}
	}
};

typedef bool (*SuccessTester)(Node*);
typedef void (*OutputSolution)(int* array, int length);

class DancingLink
{
protected:
	enum Direction
	{
		Left, Right, Up, Down
	};
	Node** stack;
	Node* head;
	int** matrix;

	int rowNumber;
	int colNumber;
	int maxBacktrackNumber;
	Node* nodeByDirection(Node* node, Direction dir);
	void doDisplay(Node* node, Direction dir);
	Node* nodeStep(Node* node, Direction dir, int step);
	void rightInsert(Node* theLeft, Node* theNode);
	void downInsert(Node* theUpper, Node* theNode);
	void horizonInsert(Node* node);
	void verticalInsert(Node* node);
	void horizonRemove(Node* node);
	void verticalRemove(Node* node);
	void deleteNode(Node* node);
	Node* createNode();
	Node* createHeader(int colNumber);
	void coverColumn(Node* colHeader);
	void uncoverColumn(Node* colHeader);
	//I prefer to make the pointer null which is safe
	void printSolution(int depth, OutputSolution outputSolution);
	void doSearch(int depth, SuccessTester successTester, OutputSolution outputSolution);
public:
	void display();
	void initialize(int** matrix, int aRowNumber, int aColNumber);
	void uninitialize();
	void search(SuccessTester successTester, OutputSolution outputSolution=NULL);
};

file name: dancingLink.cpp

#include <iostream>
#include "dancinglink.h"

using namespace std;

void DancingLink::initialize(int** aMatrix, int aRowNumber, int aColNumber)
{
	rowNumber=aRowNumber;
	colNumber=aColNumber;
	maxBacktrackNumber=colNumber;
	matrix=aMatrix;
	stack=new Node*[maxBacktrackNumber];

	head=createHeader(colNumber);
	Node* start=head->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);
				node->row=r;
				node->col=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;
			}
		}
	}
}

Node* DancingLink::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 DancingLink::doDisplay(Node* node, Direction dir)
{
	Node* ptr=node;
	while (true)
	{
		ptr=nodeByDirection(ptr, dir);
		if (ptr==node)
		{
			break;
		}
		ptr->display();
	}
}


void DancingLink::display()
{
	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* DancingLink::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->col=c;
		node->name=new char[MaxNameLength];
		sprintf(node->name, "column %d header", c);
		rightInsert(current, node);
		current=node;
	}
	return result;
}

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


Node* DancingLink::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->row=-1;
	result->col=-1;
	result->name=NULL;
	return result;
}



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

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

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

void DancingLink::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 DancingLink::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 DancingLink::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 DancingLink::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 DancingLink::uninitialize()
{
	Node* right;
	Node* lower;
	
	delete[] stack;
	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;
	stack=NULL;
}



void DancingLink::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 DancingLink::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 DancingLink::printSolution(int depth, OutputSolution outputSolution)
{
	Node* ptr;
	int i;
	if (outputSolution==NULL)
	{
		cout<<"one solution is found\n";
		for (i=0; i<depth; i++)
		{
			ptr=stack[i];
			do
			{
				cout<<ptr->C->name<<"\t";
				ptr=ptr->R;
			}
			while (ptr!=stack[i]);
			cout<<"\n";			
		}
	}
	else
	{
		int* array=new int[depth];
		for (i=0; i<depth; i++)
		{
			array[i]=stack[i]->row;
		}
		outputSolution(array, depth);
		//the user is not responsible for memory delete
		delete[]array;
	}
}

void DancingLink::doSearch(int depth, SuccessTester successTester, OutputSolution outputSolution)
{
	Node* columnHeader;	
	Node* row;
	Node* ptr;

	if (successTester(head))
	{
		printSolution(depth, outputSolution);
		return;
	}
	columnHeader=head->R;

	//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;
		}
		doSearch(depth+1, successTester, outputSolution);
		//backtrack
		row=stack[depth];
		columnHeader=row->C;
		ptr=row->L;
		while (row!=ptr)
		{
			uncoverColumn(ptr->C);
			ptr=ptr->L;
		}
		row=row->D;
	}
	uncoverColumn(columnHeader);
}

void DancingLink::search(SuccessTester successTester, OutputSolution outputSolution)
{
	doSearch(0, successTester, outputSolution);
}



//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;
}

file name: queen.h

void queen();

file name: dancingLink.cpp


#include <iostream>
#include "dancinglink.h"
#include "queen.h"

using namespace std;

const int N=8;

int** matrix;

//the matrix is like this:
//row(0 N-1), col(N 2N-1), primary(2N 4N-2), reverse(4N-3  6N-2)
const int DiagonalLength=2*N-1;
const int RowOffset=0;
const int ColOffset=N;
const int PrimaryOffset=2*N;
const int ReverseOffset=PrimaryOffset+DiagonalLength;
int rowNumber, colNumber;

int primaryIndex(int row, int col)
{
	return row+col;
}

int reverseIndex(int row, int col)
{
	return N-1-col+row;
}

void initializeMatrix()
{
	int r, c, row, col, primary, reverse;
	colNumber=(N+ 2*N-1)*2;
	rowNumber=N*N;

	matrix=new int*[rowNumber];
	for (r=0; r<rowNumber; r++)
	{
		matrix[r]=new int[colNumber];
		for (c=0; c<colNumber; c++)
		{
			matrix[r][c]=0;
		}
		row=r/N;
		col=r%N;
		primary=primaryIndex(row, col);
		reverse=reverseIndex(row, col);
		matrix[r][row+RowOffset]=1;
		matrix[r][col+ColOffset]=1;
		matrix[r][primary+PrimaryOffset]=1;
		matrix[r][reverse+ReverseOffset]=1;
	}
}

bool queenTester(Node* head)
{
	return head->R->col>=PrimaryOffset;
}

void queenOutput(int* array, int length)
{
	int i, j;
	int row, col;
	cout<<"\none solution is:\n";
	for (i=0; i<length; i++)
	{
		for (j=0; j<N; j++)
		{
			if (matrix[array[i]][j]>0)
			{
				row=j;
				break;
			}
		}
		for (j=0; j<N; j++)
		{
			if (matrix[array[i]][j+N]>0)
			{
				col=j;
				break;
			}
		}
		cout<<"queen["<<row<<"]["<<col<<"]\n";
	}
}


void printMatrix(int rowNumber, int colNumber, int**matrix)
{
	for (int r=0; r<rowNumber; r++)
	{
		for (int c=0; c<colNumber; c++)
		{
			cout<<matrix[r][c]<<",";
		}
		cout<<"\n";
	}
}

void queen()
{
	DancingLink dance;
	initializeMatrix();
	printMatrix(rowNumber, colNumber, matrix);
	dance.initialize(matrix, rowNumber, colNumber);
	//dance.display();
	dance.search(queenTester, queenOutput);
	dance.uninitialize();
}
	


file name: main.cpp



#include <iostream>
#include "dancinglink.h"
#include "queen.h"

using  namespace std;


int matrix[6][7]=
{
	{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}
};

int** createClique();
void cliqueTest();

bool cliqueTester(Node* head)
{
	return head==head->R;
}

void cliqueTest();

int main()
{
	//cliqueTest();
	queen();

	return 0;
}

void cliqueTest()
{
	DancingLink dance;
	int** clique=createClique();
	dance.initialize(clique, 6, 7);

	cout<<"\nnow let's search:\n";
	dance.search(cliqueTester);
	dance.uninitialize();
	for (int i=0; i<6; i++)
	{
		delete[]clique[i];
	}
	delete[]clique;
}

int** createClique()
{
	int** clique;
	clique=new int*[6];
	for (int r=0; r<6; r++)
	{
		clique[r]=new int[7];
		for (int c=0; c<7; c++)
		{
			clique[r][c]=matrix[r][c];
		}
	}
	return clique;
}

　
A snapshot of running automated testing: (8-queen)
1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,
1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,
1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,
1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,
1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,
1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,
0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,
0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,
0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,
0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,
0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,
0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,
0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,
0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,
0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,
0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,
0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,
0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,
0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,
0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,
0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,
0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,
0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,
0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,
0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,
0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,
0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,
0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,
0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,
0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,
0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,
0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,
0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,
0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,
0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,
0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,
0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,
0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,
0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,
0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,
0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,
0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,
0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,
0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,
0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,
0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,
0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,
0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,
0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,
0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,
0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,
0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,
0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,
0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,

one solution is:
queen[0][0]
queen[1][4]
queen[2][7]
queen[3][5]
queen[4][2]
queen[5][6]
queen[6][1]
queen[7][3]

one solution is:
queen[0][0]
queen[1][5]
queen[2][7]
queen[3][2]
queen[4][6]
queen[5][3]
queen[6][1]
queen[7][4]

one solution is:
queen[0][0]
queen[1][6]
queen[2][3]
queen[3][5]
queen[4][7]
queen[5][1]
queen[6][4]
queen[7][2]

one solution is:
queen[0][0]
queen[1][6]
queen[2][4]
queen[3][7]
queen[4][1]
queen[5][3]
queen[6][5]
queen[7][2]

one solution is:
queen[0][1]
queen[1][3]
queen[2][5]
queen[3][7]
queen[4][2]
queen[5][0]
queen[6][6]
queen[7][4]

one solution is:
queen[0][1]
queen[1][4]
queen[2][6]
queen[3][0]
queen[4][2]
queen[5][7]
queen[6][5]
queen[7][3]

one solution is:
queen[0][1]
queen[1][4]
queen[2][6]
queen[3][3]
queen[4][0]
queen[5][7]
queen[6][5]
queen[7][2]

one solution is:
queen[0][1]
queen[1][5]
queen[2][0]
queen[3][6]
queen[4][3]
queen[5][7]
queen[6][2]
queen[7][4]

one solution is:
queen[0][1]
queen[1][5]
queen[2][7]
queen[3][2]
queen[4][0]
queen[5][3]
queen[6][6]
queen[7][4]

one solution is:
queen[0][1]
queen[1][6]
queen[2][2]
queen[3][5]
queen[4][7]
queen[5][4]
queen[6][0]
queen[7][3]

one solution is:
queen[0][1]
queen[1][6]
queen[2][4]
queen[3][7]
queen[4][0]
queen[5][3]
queen[6][5]
queen[7][2]

one solution is:
queen[0][1]
queen[1][7]
queen[2][5]
queen[3][0]
queen[4][2]
queen[5][4]
queen[6][6]
queen[7][3]

one solution is:
queen[0][2]
queen[1][0]
queen[2][6]
queen[3][4]
queen[4][7]
queen[5][1]
queen[6][3]
queen[7][5]

one solution is:
queen[0][2]
queen[1][4]
queen[2][1]
queen[3][7]
queen[4][0]
queen[5][6]
queen[6][3]
queen[7][5]

one solution is:
queen[0][2]
queen[1][4]
queen[2][1]
queen[3][7]
queen[4][5]
queen[5][3]
queen[6][6]
queen[7][0]

one solution is:
queen[0][2]
queen[1][4]
queen[2][6]
queen[3][0]
queen[4][3]
queen[5][1]
queen[6][7]
queen[7][5]

one solution is:
queen[0][2]
queen[1][4]
queen[2][7]
queen[3][3]
queen[4][0]
queen[5][6]
queen[6][1]
queen[7][5]

one solution is:
queen[0][2]
queen[1][5]
queen[2][1]
queen[3][4]
queen[4][7]
queen[5][0]
queen[6][6]
queen[7][3]

one solution is:
queen[0][2]
queen[1][5]
queen[2][1]
queen[3][6]
queen[4][0]
queen[5][3]
queen[6][7]
queen[7][4]

one solution is:
queen[0][2]
queen[1][5]
queen[2][1]
queen[3][6]
queen[4][4]
queen[5][0]
queen[6][7]
queen[7][3]

one solution is:
queen[0][2]
queen[1][5]
queen[2][3]
queen[3][0]
queen[4][7]
queen[5][4]
queen[6][6]
queen[7][1]

one solution is:
queen[0][2]
queen[1][5]
queen[2][3]
queen[3][1]
queen[4][7]
queen[5][4]
queen[6][6]
queen[7][0]

one solution is:
queen[0][2]
queen[1][5]
queen[2][7]
queen[3][0]
queen[4][3]
queen[5][6]
queen[6][4]
queen[7][1]

one solution is:
queen[0][2]
queen[1][5]
queen[2][7]
queen[3][0]
queen[4][4]
queen[5][6]
queen[6][1]
queen[7][3]

one solution is:
queen[0][2]
queen[1][5]
queen[2][7]
queen[3][1]
queen[4][3]
queen[5][0]
queen[6][6]
queen[7][4]

one solution is:
queen[0][2]
queen[1][6]
queen[2][1]
queen[3][7]
queen[4][4]
queen[5][0]
queen[6][3]
queen[7][5]

one solution is:
queen[0][2]
queen[1][6]
queen[2][1]
queen[3][7]
queen[4][5]
queen[5][3]
queen[6][0]
queen[7][4]

one solution is:
queen[0][2]
queen[1][7]
queen[2][3]
queen[3][6]
queen[4][0]
queen[5][5]
queen[6][1]
queen[7][4]

one solution is:
queen[0][3]
queen[1][0]
queen[2][4]
queen[3][7]
queen[4][1]
queen[5][6]
queen[6][2]
queen[7][5]

one solution is:
queen[0][3]
queen[1][0]
queen[2][4]
queen[3][7]
queen[4][5]
queen[5][2]
queen[6][6]
queen[7][1]

one solution is:
queen[0][3]
queen[1][1]
queen[2][4]
queen[3][7]
queen[4][5]
queen[5][0]
queen[6][2]
queen[7][6]

one solution is:
queen[0][3]
queen[1][1]
queen[2][6]
queen[3][2]
queen[4][5]
queen[5][7]
queen[6][0]
queen[7][4]

one solution is:
queen[0][3]
queen[1][1]
queen[2][6]
queen[3][2]
queen[4][5]
queen[5][7]
queen[6][4]
queen[7][0]

one solution is:
queen[0][3]
queen[1][1]
queen[2][6]
queen[3][4]
queen[4][0]
queen[5][7]
queen[6][5]
queen[7][2]

one solution is:
queen[0][3]
queen[1][1]
queen[2][7]
queen[3][4]
queen[4][6]
queen[5][0]
queen[6][2]
queen[7][5]

one solution is:
queen[0][3]
queen[1][1]
queen[2][7]
queen[3][5]
queen[4][0]
queen[5][2]
queen[6][4]
queen[7][6]

one solution is:
queen[0][3]
queen[1][5]
queen[2][0]
queen[3][4]
queen[4][1]
queen[5][7]
queen[6][2]
queen[7][6]

one solution is:
queen[0][3]
queen[1][5]
queen[2][7]
queen[3][1]
queen[4][6]
queen[5][0]
queen[6][2]
queen[7][4]

one solution is:
queen[0][3]
queen[1][5]
queen[2][7]
queen[3][2]
queen[4][0]
queen[5][6]
queen[6][4]
queen[7][1]

one solution is:
queen[0][3]
queen[1][6]
queen[2][0]
queen[3][7]
queen[4][4]
queen[5][1]
queen[6][5]
queen[7][2]

one solution is:
queen[0][3]
queen[1][6]
queen[2][2]
queen[3][7]
queen[4][1]
queen[5][4]
queen[6][0]
queen[7][5]

one solution is:
queen[0][3]
queen[1][6]
queen[2][4]
queen[3][1]
queen[4][5]
queen[5][0]
queen[6][2]
queen[7][7]

one solution is:
queen[0][3]
queen[1][6]
queen[2][4]
queen[3][2]
queen[4][0]
queen[5][5]
queen[6][7]
queen[7][1]

one solution is:
queen[0][3]
queen[1][7]
queen[2][0]
queen[3][2]
queen[4][5]
queen[5][1]
queen[6][6]
queen[7][4]

one solution is:
queen[0][3]
queen[1][7]
queen[2][0]
queen[3][4]
queen[4][6]
queen[5][1]
queen[6][5]
queen[7][2]

one solution is:
queen[0][3]
queen[1][7]
queen[2][4]
queen[3][2]
queen[4][0]
queen[5][6]
queen[6][1]
queen[7][5]

one solution is:
queen[0][4]
queen[1][0]
queen[2][3]
queen[3][5]
queen[4][7]
queen[5][1]
queen[6][6]
queen[7][2]

one solution is:
queen[0][4]
queen[1][0]
queen[2][7]
queen[3][3]
queen[4][1]
queen[5][6]
queen[6][2]
queen[7][5]

one solution is:
queen[0][4]
queen[1][0]
queen[2][7]
queen[3][5]
queen[4][2]
queen[5][6]
queen[6][1]
queen[7][3]

one solution is:
queen[0][4]
queen[1][1]
queen[2][3]
queen[3][5]
queen[4][7]
queen[5][2]
queen[6][0]
queen[7][6]

one solution is:
queen[0][4]
queen[1][1]
queen[2][3]
queen[3][6]
queen[4][2]
queen[5][7]
queen[6][5]
queen[7][0]

one solution is:
queen[0][4]
queen[1][1]
queen[2][5]
queen[3][0]
queen[4][6]
queen[5][3]
queen[6][7]
queen[7][2]

one solution is:
queen[0][4]
queen[1][1]
queen[2][7]
queen[3][0]
queen[4][3]
queen[5][6]
queen[6][2]
queen[7][5]

one solution is:
queen[0][4]
queen[1][2]
queen[2][0]
queen[3][5]
queen[4][7]
queen[5][1]
queen[6][3]
queen[7][6]

one solution is:
queen[0][4]
queen[1][2]
queen[2][0]
queen[3][6]
queen[4][1]
queen[5][7]
queen[6][5]
queen[7][3]

one solution is:
queen[0][4]
queen[1][2]
queen[2][7]
queen[3][3]
queen[4][6]
queen[5][0]
queen[6][5]
queen[7][1]

one solution is:
queen[0][4]
queen[1][6]
queen[2][0]
queen[3][2]
queen[4][7]
queen[5][5]
queen[6][3]
queen[7][1]

one solution is:
queen[0][4]
queen[1][6]
queen[2][0]
queen[3][3]
queen[4][1]
queen[5][7]
queen[6][5]
queen[7][2]

one solution is:
queen[0][4]
queen[1][6]
queen[2][1]
queen[3][3]
queen[4][7]
queen[5][0]
queen[6][2]
queen[7][5]

one solution is:
queen[0][4]
queen[1][6]
queen[2][1]
queen[3][5]
queen[4][2]
queen[5][0]
queen[6][3]
queen[7][7]

one solution is:
queen[0][4]
queen[1][6]
queen[2][1]
queen[3][5]
queen[4][2]
queen[5][0]
queen[6][7]
queen[7][3]

one solution is:
queen[0][4]
queen[1][6]
queen[2][3]
queen[3][0]
queen[4][2]
queen[5][7]
queen[6][5]
queen[7][1]

one solution is:
queen[0][4]
queen[1][7]
queen[2][3]
queen[3][0]
queen[4][2]
queen[5][5]
queen[6][1]
queen[7][6]

one solution is:
queen[0][4]
queen[1][7]
queen[2][3]
queen[3][0]
queen[4][6]
queen[5][1]
queen[6][5]
queen[7][2]

one solution is:
queen[0][5]
queen[1][0]
queen[2][4]
queen[3][1]
queen[4][7]
queen[5][2]
queen[6][6]
queen[7][3]

one solution is:
queen[0][5]
queen[1][1]
queen[2][6]
queen[3][0]
queen[4][2]
queen[5][4]
queen[6][7]
queen[7][3]

one solution is:
queen[0][5]
queen[1][1]
queen[2][6]
queen[3][0]
queen[4][3]
queen[5][7]
queen[6][4]
queen[7][2]

one solution is:
queen[0][5]
queen[1][2]
queen[2][0]
queen[3][6]
queen[4][4]
queen[5][7]
queen[6][1]
queen[7][3]

one solution is:
queen[0][5]
queen[1][2]
queen[2][0]
queen[3][7]
queen[4][3]
queen[5][1]
queen[6][6]
queen[7][4]

one solution is:
queen[0][5]
queen[1][2]
queen[2][0]
queen[3][7]
queen[4][4]
queen[5][1]
queen[6][3]
queen[7][6]

one solution is:
queen[0][5]
queen[1][2]
queen[2][4]
queen[3][6]
queen[4][0]
queen[5][3]
queen[6][1]
queen[7][7]

one solution is:
queen[0][5]
queen[1][2]
queen[2][4]
queen[3][7]
queen[4][0]
queen[5][3]
queen[6][1]
queen[7][6]

one solution is:
queen[0][5]
queen[1][2]
queen[2][6]
queen[3][1]
queen[4][3]
queen[5][7]
queen[6][0]
queen[7][4]

one solution is:
queen[0][5]
queen[1][2]
queen[2][6]
queen[3][1]
queen[4][7]
queen[5][4]
queen[6][0]
queen[7][3]

one solution is:
queen[0][5]
queen[1][2]
queen[2][6]
queen[3][3]
queen[4][0]
queen[5][7]
queen[6][1]
queen[7][4]

one solution is:
queen[0][5]
queen[1][3]
queen[2][0]
queen[3][4]
queen[4][7]
queen[5][1]
queen[6][6]
queen[7][2]

one solution is:
queen[0][5]
queen[1][3]
queen[2][1]
queen[3][7]
queen[4][4]
queen[5][6]
queen[6][0]
queen[7][2]

one solution is:
queen[0][5]
queen[1][3]
queen[2][6]
queen[3][0]
queen[4][2]
queen[5][4]
queen[6][1]
queen[7][7]

one solution is:
queen[0][5]
queen[1][3]
queen[2][6]
queen[3][0]
queen[4][7]
queen[5][1]
queen[6][4]
queen[7][2]

one solution is:
queen[0][5]
queen[1][7]
queen[2][1]
queen[3][3]
queen[4][0]
queen[5][6]
queen[6][4]
queen[7][2]

one solution is:
queen[0][6]
queen[1][0]
queen[2][2]
queen[3][7]
queen[4][5]
queen[5][3]
queen[6][1]
queen[7][4]

one solution is:
queen[0][6]
queen[1][1]
queen[2][3]
queen[3][0]
queen[4][7]
queen[5][4]
queen[6][2]
queen[7][5]

one solution is:
queen[0][6]
queen[1][1]
queen[2][5]
queen[3][2]
queen[4][0]
queen[5][3]
queen[6][7]
queen[7][4]

one solution is:
queen[0][6]
queen[1][2]
queen[2][0]
queen[3][5]
queen[4][7]
queen[5][4]
queen[6][1]
queen[7][3]

one solution is:
queen[0][6]
queen[1][2]
queen[2][7]
queen[3][1]
queen[4][4]
queen[5][0]
queen[6][5]
queen[7][3]

one solution is:
queen[0][6]
queen[1][3]
queen[2][1]
queen[3][4]
queen[4][7]
queen[5][0]
queen[6][2]
queen[7][5]

one solution is:
queen[0][6]
queen[1][3]
queen[2][1]
queen[3][7]
queen[4][5]
queen[5][0]
queen[6][2]
queen[7][4]

one solution is:
queen[0][6]
queen[1][4]
queen[2][2]
queen[3][0]
queen[4][5]
queen[5][7]
queen[6][1]
queen[7][3]

one solution is:
queen[0][7]
queen[1][1]
queen[2][3]
queen[3][0]
queen[4][6]
queen[5][4]
queen[6][2]
queen[7][5]

one solution is:
queen[0][7]
queen[1][1]
queen[2][4]
queen[3][2]
queen[4][0]
queen[5][6]
queen[6][3]
queen[7][5]

one solution is:
queen[0][7]
queen[1][2]
queen[2][0]
queen[3][5]
queen[4][1]
queen[5][4]
queen[6][6]
queen[7][3]

one solution is:
queen[0][7]
queen[1][3]
queen[2][0]
queen[3][2]
queen[4][5]
queen[5][1]
queen[6][6]
queen[7][4]