８人の女王

質問

８人の女王とは
８人のクイーンを８×８のチェス盤に配置し、そのどれもが互いに行き違わないようにする置き方を求めるというものです。クイーンは縦横斜め、全ての方向に移動することができます。

置き方は、
　　board[]={x0,x1, … , xi, … , x7}
と表現します。一番左上のマスを（0,0）とすれば、各駒の座標は(i,xi(つまりboard[i]))であらわせるわけです。

自分なりに行き違う条件を求めてみました。
縦横方向を考えれば
i==j
board[i]==board[j]
斜め方向を考えれば
i+board[i]==j+board[j]
i-board[i]==j-board[j]

ただこれらを考えた上でプログラムするとなるとどうすればいいかさっぱり皆目検討もつきません＾＾；
再帰的にやるというのもわかるのですがやはりどう書けばいいか・・・
教えてくださる方よろしくおねがいします

回答No.3

nakashi · ベストアンサー

下記URLからの引用

/***********************************************************
nqueens.c -- N王妃の問題
***********************************************************/
#include <stdio.h>
#include <stdlib.h>

#define N 8 /* N×N の盤面 */
int a[N], b[2 * N - 1], c[2 * N - 1], x[N];

void found(void)
{
int i, j;
static solution = 0;

printf("\n解 %d\n", ++solution);
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++)
if (x[i] == j) printf(" Q");
else printf(" .");
printf("\n");
}
}

void try(int i)
{
int j;

for (j = 0; j < N; j++)
if (a[j] && b[i + j] && c[i - j + N - 1]) {
x[i] = j;
if (i < N - 1) {
a[j] = b[i + j] = c[i - j + N - 1] = 0;
try(i + 1);
a[j] = b[i + j] = c[i - j + N - 1] = 1;
} else found();
}
}

int main()
{
int i;

for (i = 0; i < N; i++) a[i] = 1;
for (i = 0; i < 2 * N - 1; i++) b[i] = 1;
for (i = 0; i < 2 * N - 1; i++) c[i] = 1;
try(0);
return EXIT_SUCCESS;
}

参考URL：

ftp://ftp.matsusaka-u.ac.jp/pub/algorithms/src/nqueens.c

回答No.2

uyama33

コンピュータ・サイエンス研究書シリーズ
アルゴリズム＋データ構造＝プログラム
Niklauth Wirth著 片山卓也訳 420頁 6,000円.

に書いてあると思います。

回答No.1

rara_sun

専門家でないので、私的な考えなんですが・・。
こんな考え方になるのでしょうか？

８×８のフラグ用配列を用意するか、
８人分の２次元位置情報を保管する配列を用意する。

各種変数や配列初期化。
(1) １個目所置き場所を決めて置いてあげる。
(2) ２個目以降次の手順で置いていく
(2)－1．順に空いているところに置く
置いていけない場所でないことをフラグから判断
（このフラグについては(2)－３でわかります）
(2)－2. 置いた場所の周りの座標に、女王がいるか調べる。
(2)－３．女王が居たらその位置に置けないというフラグを立てる。女王が居なかったら、置いた事にする。
(2)－４．次の空いている場所に移動して、次の女王の置き場所を決めるために(2)－１へ戻る。置いていけない場所フラグなどから空いている場所が無い場合は、終了するか、(1)の置いた場所以外の置き場所からスタートして(1)の手順から処理を進める。

なんか・・・わかりずらいですかね？
自信無いので雰囲気だけでも・・・。