８人の女王

質問

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

置き方は、
　　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