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

Question

プログラミング初心者です。
ｃ言語を独学で進めていたのですが、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/ツールのバージョンなど）

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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;