スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

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

チェスにおいて、クイーンの駒は縦・横・斜めの 8 方向に任意のマスの数だけ動かすことができます。エイト・クイーン問題とは、8×8 マスの盤上に 8 個のクイーンを互いに他の駒に取られないように配置せよ、という問題です。解は全部で 92 個あり、回転と鏡映の操作で一致するものを同一視すると 12 個であることが知られています。

プログラム例 (1)

バックトラック法 (=手順を進められるだけ進めていき、行き詰ったら一つ前に戻ってやり直すやり方) によって全ての解を求める C++ プログラム。

#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 check( const vector<int>& queen, const int i, const int j )
{
  for ( int k = 0; k < i; k++ ) {
    // 縦方向
    if ( queen[k] == j ) { return false; }
    // 斜め方向 (左上から右下へ)
    if ( k - queen[k] == i - j ) { return false; }
    // 斜め方向 (右上から左下へ)
    if ( k + queen[k] == i + j ) { return false; }
  }
  return true;
}

void searchSolution(
  const unsigned int N, const int i, int* pCount )
{
  static vector<int> queen( N, -1 );  // クイーンの各行に対する位置

  if ( i == N ) {  // 解が見つかったとき
    printSolution( queen );
    (*pCount)++;
    return;
  }

  for ( int j = 0; j < N; j++ ) {
    if ( check( queen, i, j ) ) {
      queen[i] = j;  // (i, j)-成分にクイーンを置く
      searchSolution( N, i + 1, pCount );  // 1行進める
      queen[i] = -1;  // クイーンを戻す
    }
  }
}

int main()
{
  const unsigned int N = 8;    // クイーンの数
  int count = 0;  // 解の個数

  searchSolution( N, 0, &count );

  cout << "total: " << count << endl;

  return 0;
}

チェス盤のマスの座標は、左上が (0, 0) で、x 軸は右方向、y 軸は下方向が正であるように割り振られているものとします。そのとき、二つのマス (a, b)、(c, d) が、同一の左上から右下への直線上にあるための (必要十分) 条件は a-b=c-d であり、同一の右上から左下への直線上にあるためのあるための条件は a+b=c+d であることです。

クイーンの射程をチェックする際、本来なら縦・横・斜めのチェックが必要ですが、行単位で駒を置いているので、横方向は省略できます。

プログラム例 (2)

プログラム例 (1) と同じく、バックトラック法によるもの。

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

void searchSolution( 
  const unsigned int N, const int i, int* pCount )
{
  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 ) {  // 解が見つかったとき
    printSolution( queen );
    (*pCount)++;
    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, pCount ); 

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

int main()
{
  const unsigned int N = 8;    // クイーンの数
  int count = 0;  // 解の個数

  searchSolution( N, 0, &count ); 

  cout << "total: " << count << endl;

  return 0;
}

クイーンの射程を記録しておく配列を用意することで、記憶領域を消費する代わりに、クイーンが置けるかどうかを判定する処理が簡単になっています。

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

プロフィール

よしいず

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

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

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

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

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

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。