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]
![]()
![]()