n皇后问题的时间代价除了递归和回溯需要的外，在每一步判断加入的皇后是否与当前棋盘格局冲突也需要不少时间，guarded函数需要扫描所在列以及两条对角线。然而我们可以通过改进数据结构来使后者的时间代价降低为O(1)。

//queens.h
static const int MAX_SIZE = 20;

class queens
{
public:
queens(const int & size);
void remove(const int & col);
bool guarded(const int & col);
bool finished();
void print();
int size;
private:
int count;
int array[MAX_SIZE];
bool downward[MAX_SIZE*2-1];
bool upward[MAX_SIZE*2-1];
bool cols[MAX_SIZE];
};

//queens.cpp
#include "queens.h"
#include <iostream>
using namespace std;

queens::queens(const int & size)
{
this->size = size;
count = 0;
for(int i=0; i<MAX_SIZE; i++)
cols[i] = false;
for(i=0; i<MAX_SIZE*2-1; i++)
upward[i] = downward[i] = false;
for(i=0; i<MAX_SIZE; i++)
array[i] = -1;
}

{
array[count] = col;
cols[col] = downward[size-1-(count-col)] = upward[count+col] = true;
++count;
}

void queens::remove(const int & col)
{
array[--count] = -1;
cols[col] = downward[size-1-(count-col)] = upward[count+col] = false;
}

bool queens::guarded(const int & col)
{
if( cols[col] || downward[size-1-(count-col)] || upward[count+col] )
return true;
return false;
}

bool queens::finished()
{
return count==size ? true : false;
}

void queens::print()
{
static int num = 0;
++num;
cout<<"solution "<<num<<endl;
for(int i=0; i<size; i++)
{
for(int j=0; j<size; j++)
if( j == array[i] )
cout<<"1  ";
else
cout<<"0  ";
cout<<endl;
}
cout<<endl<<endl<<endl;
}

//test.cpp
#include <iostream>
#include "queens.h"

using namespace std;

void chess_board( queens config )
{
if( config.finished() )
config.print();
else
for(int i=0; i<config.size; i++)
if( !config.guarded(i) )
{