菜鸟天堂

n皇后问题是递归和回溯法的一个典型应用。问题描述如下：对于一个n×n的棋盘，要求在其中放入互不攻击的n个皇后。皇后的攻击范围包括：
1) 同一行
2) 同一列
3) 同一对角线（包括两个方向）

分析后可见，皇后之间互不攻击当且仅当满足下列条件：
1) 每一行只能有一个皇后
2) 每一列只能有一个皇后
3) 任意条对角线上面只能有一个皇后

若按照从左到右从上到下的顺序手动摆放皇后，会发现算法遵循的是回溯法的思想。于是我们遵循top-down design的顺序来设计整个算法和程序。

采用OOP的思想，先假设存在一个·表示棋盘格局的类queens，则定义回溯函数solve_from(queens configuration)，configuration表示当前棋盘格局，算法不断扩展棋盘的当前格局（找到下一个非冲突位置），当找到一个解决方案时打印该方案。该递归函数采用回溯法求出所有解。main函数调用solve_from时传递的实参是一个空棋盘。

对于模拟棋盘的queens类，我们可以定义三个数据成员：
1) size：棋盘的边长，即大小
2) count：已放置的互不冲突的皇后数
3) array[][]：布尔矩阵，true表示当前格有皇后

这里需要稍加思考以便稍后可以简化程序：因为每行只能放一个皇后，从上到下，从左到右放，那么count个皇后占用的行为0——count－1。所以 count还表示下一个皇后应该添加在哪一行。这样，add和remove操作的入口参数就只需要提供列号就行了，降低了耦合度 ：）

为了模拟棋盘操作，应该至少提供以下方法：
1) 初始化一个size大小的空棋盘queens(int size)
2) 插入一个非冲突的皇后add( int col )
3) 删除最新插入的皇后remove( int col )
4) 判断要插入的皇后是否与已存在的棋盘格局相冲突bool guarded( int col )
5) 判断是否棋盘已满bool finished( )
6) 若棋盘已满则打印棋盘格局print()

于是solve_from定义如下：
void solve_from( queens &configuration )
{
      if( configuration.finished() )
            configuration.print();
      else
            for( int i=0; i<size; i++ )
                  if( !configuration.guarded( i ) )
                  {
                        configuration.add( i );
                        solve_from(configuration);
                        configuration.remove( i );
                  }
}

queens的方法实现如下：
static const int MAX_SIZE = 20
queens::queens( const int & size )
{
      for( int i=0; i<MAX_SIZE; i++ )
           for( int j=0; j<MAX_SIZE; j++ )
                  array[ i ][ j ] = false;
      this->size = size;
      count = 0;      
}

void queens::add( const int & col )
{
      array[ count++ ][ col ] = true;
}

void queens::remove( const int & col )
{
      array[ --count ][ col ] = false;
}

关于guarded还有一点说明：
由于回溯法中的剪枝函数configuration.remove保证了每行只有一个皇后，我们是需要判断列冲突与对角线冲突的情况。而且由递归的顺序是从上到下从左到右，所以我们也不需要判断下方的列和对角线，也就是说只要判断三个方向：
current——top
current——upper-left
current——upper-right
工作量就减少了一半以上。

bool queens::guarded( const int & col )
{
      bool gu = false;
      // current——top
      for( int i=0; !gu&&i<count; i++ )
           gu = array[ i ][ col ];
      // current——up-left
      for( i=1; !gu&&(count-i>=0)&&(col-i>=0); i++ )
           gu = array[ count-i ][ col-i ];
      // current——up-right
      for( i=1; !gu&&(count-i>=0)&&(col+i<=size; i++ )
           gu = array[ count-i ][ col+i ];
      return gu;
}

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

bool 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++ )
                cout<<array[ i ][ j ]<<"   ";
           cout<<endl;
      }
      cout<<endl<<endl<<endl;              
}