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