エイト・クイーン問題を解くC++プログラムの例 (2)

前回のプログラム例に、鏡映と回転の操作について対称な解をチェックする処理を追加。

プログラム例

ある解が見つかったら、その解を記憶すると同時に回転や鏡映の操作について対称な解を生成して記憶しておきます。それらの解を、次に見つかった解と比較することにより、重複をチェックします。

#include <iostream>
#include <vector>

using namespace std;

void printSolution( const vector<int>& queen ) 
{ 
  for ( int i = 0; i < queen.size(); i++ ) {
    cout << queen[i] << " ";
  }
  cout << endl;
}

bool isEqual( 
  const vector<int>& q1, 
  const vector<int>& q2 ) 
{
  if ( q1.size() != q2.size() ) { return false; }

  for( int i = 0; i < q1.size(); i++ ) {
    if( q1[i] != q2[i] ) { return false; }
  }

  return true;
}

bool checkDupl( 
  const vector< vector<int> >& sols, 
  const vector<int>& q ) 
{
  for ( int i = 0; i < sols.size(); i++ ) {
    if ( isEqual( sols[i], q ) ) { return true; }
  }

  return false;
}

void identifySymmetries(
  vector<int>& queen,
  vector< vector<int> >& sols,
  vector< vector<int> >& fundsols ) 
{
  const unsigned int N = queen.size();

  if ( !checkDupl( sols, queen ) ) {  // 解が既出でないとき
    printSolution( queen );
    fundsols.push_back ( queen );
    sols.push_back( queen );

    vector< vector<int> > var( 7, vector<int>(N) );  // 対称な解

    for( int i = 0; i < N; i++ ) { 
      // 鏡映
      var[0][N-1-i] = queen[i]; 
      var[1][i] = N-1-queen[i]; 
      var[2][queen[i]] = i; 
      var[3][N-1-queen[i]] = N-1-i; 
      // 回転
      var[4][N-1-queen[i]] = i;
      var[5][N-1-i] = N-1-queen[i];
      var[6][queen[i]] = N-1-i;
    }

    for( int i = 0; i < 7; i++ ) { 
      if ( !checkDupl( sols, var[i] ) ) { sols.push_back( var[i] ); }
    }
  }
}

void searchSolution( 
  const unsigned int N, const int i, 
  vector< vector<int> >& sols,
  vector< vector<int> >& fundsols ) 
{
  static vector<int>  queen( N, -1 );  // クイーンの各行に対する位置
  static vector<char> vertical( N, 0 );     // 縦方向
  static vector<char> leftDiag( 2*N, 0 );   // 斜め(左上から右下)
  static vector<char> rightDiag( 2*N, 0 );  // 斜め(右上から左下)

  if ( i == N ) {  // 解が見つかったとき
    identifySymmetries( queen, sols, fundsols );
    return;
  } 

  for ( int j = 0; j < N; j++ ) {
    // 他のクイーンの射程にあるとき
    if ( vertical[j] == 1 ) { continue; }
    if ( leftDiag[i-j+N-1] == 1 ) { continue; }
    if ( rightDiag[i+j] == 1 ) { continue; }

    // (i, j)-成分にクイーンを置く
    queen[i] = j;
    vertical[j] = 1;
    leftDiag[i-j+N-1] = 1;
    rightDiag[i+j] = 1;

    // 1行進める
    searchSolution( N, i + 1, sols, fundsols ); 

    // クイーンを戻す
    vertical[j] = 0;
    leftDiag[i-j+N-1] = 0;
    rightDiag[i+j] = 0;
  }
}

int main()
{
  const unsigned int N = 8;        // クイーンの数
  vector< vector<int> > sols;      // すべての解を格納する配列
  vector< vector<int> > fundsols;  // 対称なものを除く解を格納する配列

  searchSolution( N, 0, sols, fundsols );

  cout << "number of fundamental solutions: " 
       << fundsols.size() << endl;
  cout << "total number of solutions: " 
       << sols.size() << endl;

  return 0;
}

【theme : プログラミング
【genre : コンピュータ

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示