10クイーン(Nクイーン)問題(C言語)の再帰関数による解法(アルゴリズム)について解説して下さい(コード提出済み)

Question

前提

該当のソースコードに記載した10クイーン問題の再帰関数による解法（アルゴリズム）をわかりやすく解説して下さい。

実現したいこと

以下のソースコードの「alg関数」がどのようなアルゴリズムとなっているのか、できればわかりやすく説明していただくことはできますか？
特に、alg関数の「while (j < queen && i != tab[j] && abs(tab[j] - i) != queen - j)」以降の部分が何をしているのか理解することができておりません。
何卒宜しくお願い致します。

試したこと

以下のソースコードを実行すると以下の結果が出力されます。

0257948136
0258693147
0258693174
0286931475
0358297146
(中略)
9713068524
9741306825
9741306852
9742051863

10×10の盤のどの行にクイーンが配置されているかの結果が出力されていることは理解できています。
例えば最初の出力の0257948136は、0列目の0行目の位置、1列目の2行目の位置、2列目の5行目の位置、3列目7行目の位置....にクイーンが置かれていることを示している。

該当のソースコード

#include <unistd.h>

void	outputchar(char c)
{
	write(1, &c, 1);
}

int	abs(int n)
{
	if (n > 0)
		return (n);
	else
		return (n * -1);
}

void	alg(char *tab, int queen, int *t_out)
{
	int	i;
	int	j;

	if (queen == 10)
	{
		queen = 0;
		while (queen < 10)
			outputchar(tab[queen++] + 48);
		outputchar('\n');
		(*t_out)++;
		return ;
	}
	i = -1;
	while (++i < 10)
	{
		j = 0;
		while (j < queen && i != tab[j] && abs(tab[j] - i) != queen - j)
			j++;
		if (j >= queen)
		{
			tab[queen] = i;
			alg(tab, queen + 1, t_out);
		}
	}
}

int	ten_queens_puzzle(void)
{
	char	arr[10];
	int		que;
	int		total_out;

	que = 0;
	total_out = 0;
	alg(arr, que, &total_out);
	return (total_out);
}

int	main(void)
{
	ten_queens_puzzle();
	return (0);
}

Comments

[jimbe]

ご自身で考えて書いたコードでは無いということでしょうか。
(わざと分かり難く書いているような感じがしますが。)

[usan]

そうなのです。
確かに理解しにくいです。
しかし、このような質問の仕方はあまりよろしくないということですね。

[fana]

そもそも真っ当なコードなのですか？
ぱっと見で，件の関数は int i; の未初期化がヤバそうに見えるのですが…？

[usan]

出力例を追記しましたが、このコードでは、10クイーン問題の724通りの配置方法を出力することが出来ています。

[fana]

あ，見間違いでした．すみません．
i = -1;
って普通に書いてありますね．（とてもはずかしい）

[jimbe]

i=-1 がありますけど。
Nクイーンは総当たりやバックトラック(今回はこれでしょうね)の解説記事が多くあると思うのですが、それらは参考にならなかったでしょうか。

[usan]

ご回答ありがとうございます。バックトラックの記事を参考にさせて頂きます。

Answer 1

弄り過ぎて(見た目)別物になってしまってます・・・。

#include <stdio.h>

#define N 10

//表示
void print(int *table) {
  for(int i=0; i<N; i++) putchar(table[i] + '0');
  putchar('\n');
}
// i と j が横に衝突していたら !0
int collisionSideways(int *table, int i, int j) {
  return table[i] == table[j]; //行が同じ
}
// i と j が斜めに衝突していたら !0
int collisionDiagonally(int *table, int i, int j) {
  return abs(table[i] - table[j]) == abs(i - j); //行と列のそれぞれの差の絶対値が同じなら衝突 Ex: (1,2)-(3,4), (1,7)-(4,4)
}
//クイーン衝突判定(column と 0～column-1 の何れかとが衝突していたら !0)
int judgment(int *table, int column) {
  int collision = 0; //衝突無
  for(int j=0; j<column && !collision; j++) {
    collision = collisionSideways(table, column, j) || collisionDiagonally(table, column, j);
  }
  return collision;
}

int alg(int *table, int column) {
  if(column == N) { //全部終わっていたら表示
    print(table);
    return 1;
  }

  int count = 0;
  for(int row=0; row<N; row++) {
    table[column] = row;
    if(!judgment(table, column)) count += alg(table, column+1); //衝突していなければ次の列
  }
  return count;
}

int main(void) {
  int table[N];
  printf("count=%d\n", alg(table, 0));
}

実行結果

0257948136
0258693147
0258693174
0286931475
0358297146
(中略)
9641702853
9713068524
9741306825
9741306852
9742051863
count=724

Comments

[usan]

大変参考になります！
こちらの解法も理解できるように努めます！！
ご回答いただきありがとうございます！

Answer 2

読み難いものは，同等の読みやすいものに書き換えていくと把握しやすいのではないでしょうか．
こんな話かと．

（t_out は使われていないので取っ払いました）

void alg(char *tab, int queen /*, int *t_out*/)
{
	//結果出力
	if (queen == 10)
	{
		queen = 0;
		while (queen < 10)
			putchar(tab[queen++] + 48);
		putchar('\n');
		//(*t_out)++;
		return ;
	}

	//この列の全候補（１０個のマス）について処理する
	for( int iPos=0; iPos<10; ++iPos )
	{
		//queen列目のクイーンを
		//iPos番目のマス（行）に置けるであろうか？
		//これは直前の列までに配置されたクイーンの場所を見て判断する
		//（：tab[0] から tab[queen-1] の内容を見てチェック）
		int itab = 0;
		for( /*NOP*/; itab<queen; ++itab )
		{
			if( iPos == tab[itab] )break;	//既存クイーンと同じ行には並べられない
			if( abs( tab[itab]-iPos ) == queen - itab )break;	//既存クイーンと斜めの位置には並べられない
		}

		//↑で途中でbreakした場合，itabの値はqueenの値に達していない．
		//すなわち，ここのifは，「iPos番目にクイーンを置けるなら」という条件．
		if(itab >= queen)
		{
			tab[queen] = iPos;	//結果を格納
			alg(tab, queen + 1 /*, t_out*/);	//次の列へ
		}
	}
}

Comments

[fana]

変数 i と j は見間違いやすいのでてきとーに別の名前に変えた．

[usan]

詳細にご回答いただきありがとうございます！！
参考にさせて頂き、今から理解に努めます！！！

[usan]

こちらの回答で先に理解するに至りました。
お二方にお答えいただいてどちらの回答にも感謝しております。
ありがとうございました。