backtrack by doubly-link

N-Queen (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.
¡¡
The N-Queen problem:
It should be known to every student of computer science.
¡¡
¡¡
¡¡
C.The idea of program
¡¡

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

This version simply makes the dancing link a class. The success testing and customized output function are all callbacks.

¡¡

    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]