質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.92%

C言語でのNクイーン問題が解けません

受付中

回答 3

投稿

  • 評価
  • クリップ 0
  • VIEW 308
退会済みユーザー

退会済みユーザー

プログラミング初心者です。
c言語を独学で進めていたのですが、Nクイーン問題で行き詰りました。
以下のようなコードを書いたのですが、問題点がわかりません。出力が以下のようになる理由はわかるのですが、どこをどう改善すればいいのかわかりません。

出力:
Q***
Q***
Q***
Q***
Q***
Q***
Q***
Q***

ご教授願います。

該当のソースコード

C言語

#include<stdio.h>
#include<stdlib.h>

#define N 8
enum {queen = 1, non = 0};

int output(int a[N][N]){

 for (int i=0; i<N; i++){
    for (int j=0; j<N; j++){   
      if (a[i][j] == non) putchar('*');
      else putchar('Q');
    }
    putchar('\n');
  }
  return 0;
}

int can_choose(int a[N][N], int i, int j){
  int x, y;

  for(x=j-1, y=i-1; x>=0 && y>=0; x--,y--)
    if(a[y][x] == queen) return 0; 

  for(x=j-1, y=i; x>=0 ; x--)
    if(a[y][x] == queen) return 0; 

  for(x=j-1, y=i+1; x>=0 && y<0; x--,y++)
    if(a[y][x] == queen) return 0; 

  return 1;
}

int solve(int board[N][N], int x){
  int y = 0;
  for(y = 0 ; y < N; y++){
    board[x][y] = queen;

      //back track
    if (can_choose(board, x, y) == 0) return 0;

      // base case
    if (can_choose(board, x, y) == 1 && x == N){
      output(board);
    }

    //recursive case
    solve(board, x+1);
  }
}

int main(){
  int x=0;
  int y=0;
  int  board[N][N];
  for (x=0; x<N; x++){
    for (y=0; y<N; y++){ 
      board[x][y] = non;
    }
  }
  solve(board, 0 );
  return 0;
}

試したこと

ここに問題に対して試したことを記載してください。

補足情報(FW/ツールのバージョンなど)

ここにより詳細な情報を記載してください。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

0

main では a[x][y]、can_choose では a[y][x] になっています。
can_choose の 3つめの for文の y<0 は常に成立しません。
solve も変です。boad[x][y] = queen; はしているのに、
non に戻す処理がありません。

ということで、書き直してみました。

#include <stdio.h>

#define N 8

enum { queen = 1, non = 0 };

int output(int a[N][N])
{
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (a[i][j] == non) printf(" *");
            else printf(" Q");
        }
        putchar('\n');
    }
    putchar('\n');
    return 0;
}

int can_choose(int a[N][N], int i, int j)
{
    int x, y;

    for (x = i - 1, y = j - 1; x >= 0 && y >= 0; x--, y--)
        if (a[x][y] == queen) return 0;

    for (x = i - 1, y = j; x >= 0; x--)
        if (a[x][y] == queen) return 0;

    for (x = j - 1, y = i + 1; x >= 0 && y < N; x--, y++)
        if (a[x][y] == queen) return 0;

    return 1;
}

int solve(int board[N][N], int x)
{
    if (x == N)
        output(board);
    else {
        for (int y = 0; y < N; y++) {
            if (can_choose(board, x, y)) {
                board[x][y] = queen;
                solve(board, x + 1);
                board[x][y] = non;
            }
        }
    }
}

int main(void)
{
    int board[N][N];
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++) {
            board[x][y] = non;
        }
    }
    solve(board, 0);
    return 0;
}


追記
別解を考えて書いてみたら、92個のパターンが出てきました。
ところが、最初のコードは、650個出てきて間違ったものが含まれています。
どこが間違っているのか調査したいんですが、ちょっと別件の用事があって
しばらく時間をください。

別解

#include <stdio.h>

#define N 8

void output(int a[])
{
    for (int i = 0; i < N; i++) {
        for (int j = 1; j <= N; j++) {
            if (a[i] == j) printf(" Q");
            else printf(" *");
        }
        putchar('\n');
    }
    putchar('\n');
}

int can_choose(int a[], int x, int y)
{
    for (int i = x - 1, p = 1; i >= 0; i--, p++)
        if (a[i] == y || a[i] - p == y || a[i] + p == y) return 0;
    return 1;
}

void solve(int board[], int x)
{
    if (x == N)
        output(board);
    else {
        for (int y = 1; y <= N; y++) {
            if (can_choose(board, x, y)) {
                board[x] = y;
                solve(board, x + 1);
                board[x] = 0;
            }
        }
    }
}

int main(void)
{
    int board[N] = { 0 };
    solve(board, 0);
}


追記2
can_choose の 3番目の for文が間違っていました。
次のように訂正します。

-     for (x = j - 1, y = i + 1; x >= 0 && y < N; x--, y++)
+     for (x = i - 1, y = j + 1; x >= 0 && y < N; x--, y++)


追記3
別解の can_choose をちょっと変更。

-    for (int i = x - 1, p = 1; i >= 0; i--, p++)
-        if (a[i] == y || a[i] - p == y || a[i] + p == y) return 0;
+    for (int p = 1; --x >= 0; p++)
+        if (a[x] == y || a[x] - p == y || a[x] + p == y) return 0;

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

まずはデバッグできる環境を揃えましょう
Eclipseや、WindowsならVisualStudioなど。
コードの任意の行で実行を止め、変数の中身を参照できます。
また、そこから1行づつ実行させてコードの流れや変数の変化を見ることができます

そうすれば、アテずっぽでコードを書かなくて済むようになり、
なぜ動かないか他人に聞くようなこともしないで済むようになります

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

こんにちは。
スマートフォンから失礼します。

初投稿ですが、この問題、Nが8のとき、
92個が正解だったと思います。

コードは持っていますが貼り付け方がわからず、
スミマセン。あまりに有名な問題だったもので。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.92%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る