C言語 Nクイーン問題 判定がうまくいきません

Question

C言語で、チェス盤にクイーンを、互いにかち合わないように置いていくプログラムを書いています（いわゆる『Nクイーン問題』です）。

再帰的な書き方が望ましいのだとは思うのですが、まず列ごとに個別で関数を作ってみたところ、３列目でハマってしまいました。

該当のソースコード

#include <stdio.h>

int board[3];

void solve2() { // 2列目
  int i, j;

  for (i = 0; i < 8; i++) {
    for (j = 0; j < 2; j++) { // １列目と２列目との重複を判定
      if (board[j] == i) continue;
      if (j - board[j] == 2 - i) continue;
      if (j + board[j] == 2 + i) continue;
      board[2] = i;
      for (j = 0; j < 3; j++) printf("%d ", board[j]);
      printf("\n");
    }
  }
}

void solve1() { // 1列目
  int i, j;

  for (i = 0; i < 8; i++) {
    for (j = 0; j < 1; j++) { // １列目との重複を判定
      if (board[j] == i) continue;
      if (j - board[j] == 1 - i) continue;
      if (j + board[j] == 1 + i) continue;
      board[1] = i;
      solve2();
    }
  }
}

void solve0() { // 0列目
  int i; // 0列目の上から何番目のマスか

  for (i = 0; i < 8; i++) {
    board[0] = i;
    solve1();
  }
}

int main(void) { solve0(); }

こちらを実行すると、出力結果が

0 2 0
0 2 1
0 2 3
0 2 4
0 2 5
0 2 6
0 2 7
0 3 0
0 3 1
0 3 3

と続いていき、どこを見ても１列目と２列目の判定は正しくなされているものの、３列目に出てくる数字はそれ以前の列との重なりを正しく判定してくれません。

どこが間違っているのか、いくら考えてもわからず煮詰まってしまったため、teratailに初めて投稿させて頂きました。

先輩の皆様にご教示頂けましたなら幸いです。どうぞよろしくお願いいたします。

Answer 1

solve2() の中でループカウンタ j が重複しています。

なお、全部見たわけではないので、他にもバグがある可能性はあります。

追記

solve1() と solve2() の中の continue をすべて break に変えてください。
理由は、説明するのが面倒くさいロジックをよく考えればわかると思うので、ご自身でお考えください。

ちなみに、solve1() の方は continue のままでも正常に動作しますが、ループ回数が 1回だけだからであり、たまたまうまく行っているだけです。

追記2

break に変えた上で、以下の行を追加してください（solve1() の方も同様に）。

void solve2() {
  int i, j, k;

  for (i = 0; i < 8; i++) {
    for (j = 0; j < 2; j++) {
      if (board[j] == i) break;
      if (j - board[j] == 2 - i) break;
      if (j + board[j] == 2 + i) break;
      board[2] = i;
      for (k = 0; k < 3; k++) printf("%d ", board[k]);
      printf("\n");
    }
    if (k < 2) continue;  // この行を追加。
  }
}

Comments

[unstoppa61e]

ご回答ありがとうございます。

確かに j が重複していたのですが、そちらを以下のように変更させて頂いても、出力結果は先ほどと変わりませんでした（理解が間違っていましたならごめんなさい）。

```c
#include <stdio.h>

int board[3];

void solve2() {
int i, j, k;

for (i = 0; i < 8; i++) {
for (j = 0; j < 2; j++) {
if (board[j] == i) continue;
if (j - board[j] == 2 - i) continue;
if (j + board[j] == 2 + i) continue;
board[2] = i;
for (k = 0; k < 3; k++) printf("%d ", board[k]);
printf("\n");
}
}
}

void solve1() {
int i, j;

for (i = 0; i < 8; i++) {
for (j = 0; j < 1; j++) {
if (board[j] == i) continue;
if (j - board[j] == 1 - i) continue;
if (j + board[j] == 1 + i) continue;
board[1] = i;
solve2();
}
}
}

void solve0() {
int i, j;

for (i = 0; i < 8; i++) {
board[0] = i;
solve1();
}
}

int main(void) { solve0(); }
```

もしも改めてご教示頂けましたなら幸いです。

[unstoppa61e]

改めてのご回答、感謝致します。

ご指示頂きました通り、全て continue を break に変更させて頂いたのですが、出力結果は先ほどと少し違うものになったものの、まだうまくいきませんでした。

《コード》
#include <stdio.h>

int board[3];

void solve2() {
int i, j, k;

for (i = 0; i < 8; i++) {
for (j = 0; j < 2; j++) {
if (board[j] == i) break;
if (j - board[j] == 2 - i) break;
if (j + board[j] == 2 + i) break;
board[2] = i;
for (k = 0; k < 3; k++) printf("%d ", board[k]);
printf("\n");
}
}
}

void solve1() {
int i, j;

for (i = 0; i < 8; i++) {
for (j = 0; j < 1; j++) {
if (board[j] == i) break;
if (j - board[j] == 1 - i) break;
if (j + board[j] == 1 + i) break;
board[1] = i;
solve2();
}
}
}

void solve0() {
int i, j;

for (i = 0; i < 8; i++) {
board[0] = i;
solve1();
}
}

int main(void) { solve0(); }

《出力結果》
0 2 1
0 2 3
0 2 4
0 2 4
0 2 5
0 2 5
0 2 6
0 2 6
0 2 7

何度もご回答頂くのは恐縮ですが、もしも再度教えを請わせて頂けましたなら幸いです。

[unstoppa61e]

ご指示を参考にして、無事に動きました！

長らくご丁寧にお付き合い頂いてご教示くださいましたこと、心より感謝申し上げます。