n皇后问题实现

Posted on 2006-08-28 18:44 樱木 阅读(354) 评论(0)  编辑 收藏 引用 所属分类: 算法与数据结构

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;              
}

只有注册用户登录后才能发表评论。