菜鸟天堂

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

对于n皇后问题来说，每一行每一列每条对角线上最多有一个皇后，那么对于这样的每个元素（行、列或对角线）我们可以用一个bool值来表示是否已经有皇后在该元素上，这样判断是否冲突就变得十分简单，只需要读取一个bool值。另外需要记录棋盘的格局，考虑到一行只有一个皇后，可以建议一个一维数组保存每一行的皇后占用的列号。

这样基本就OK了，只是对于行而言，我们采用了回溯法（剪枝函数）保证了每行只有一个皇后，这样行的bool数组就可以省略了。

整个程序的实现如下：
//queens.h
static const int MAX_SIZE = 20;

class queens
{
public:
 queens(const int & size);
 void add(const int & col);
 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;
}

void queens::add(const int & col)
{
 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) )
   {
    config.add(i);
    chess_board(config);
    config.remove(i);
   } 
}

int main()
{
 queens configuration(8);
 chess_board(configuration);
}