08 The ten queens

注意:https://chanhuiseok.github.io/posts/baek-1/
youtube : n-queens problem

条件...?

通常はN*Nチェス盤(4<=N<=15)
N個の皇后を一緒に置いて、お互いに攻撃できないのであれば、数量を求める問題です.
++42ソウル:
1.皇后の位置を文字列で表す、
2.すべてのメソッドの合計数を返す必要があります.
Queenは、同じ行、同じ列、対角線/、方向が離せないという特徴があります.
->行ごとにQueenを配置し、フィーチャーの1つである行を考慮しないようにします.

では、対角線はどう判断するのか…？

xとyが同時に増加または減少した場合、この対角線が見つかります!

\
 \
  \
   \

この対角線はxを小さくしy値を大きくすることができる.
xを増やしてy値を減らすと見つかります!

   /
  /
 /
/

この場合、2つの条件に共通点があります:)
4*4地図上では、(2,1)に皇后が...
では(3、2)、(1、0)、
(1、2)、(0、3)および(3、0)は対角線に対応する.
|3 - 2| = |2 - 1|
|1 - 2| = |1 - 0|
|1 - 2| = |2 - 1|
ちょっと待って.

これらの値の絶対値|行番号差異|=|列番号差異|は同じです。

行番号の違い==列番号の違い=>同じ対角線上に!

△小学校、中学校で学んだ直線方程式y=x,y=-xを考えてみましょう.
また、問題では1次元文字列で表示して出力する必要があります.

アレイを使用して説明します.
0列(索引)の後の位置(行).第1列(索引)Queenの位置(行)
一行皇后の位置、二行皇后の位置.このように使えるので、1次元アレイでも十分です.
(==配列のインデックスを情報として使用!!)
問題は列皇后の位置(行)が表示されていることです.
同じローは表示されません.インデックス-インデックス==ロー-ローインデックス値は表示されません.
1142 = X !!! (行は同じ場所に置いてありました!!)
1423 = X !!! (2番目と3番目のインデックス差=1、2番目と3番目のロー差=1!)
もしそうであれば、次の条件が適用されます.

if (queen[i] != queen[cnt], i - cnt != queen[i] - queen[cnt])

できるはずです.

じょうけんけってい

int	judge(int x, char *board)
{
	int		i;
    int		tmp;
    
    i = 0;
    while (i < x)
    {
    	tmp = board[x] - board[i];
        if (tmp < 0)
        	tmp *= -1;
    	if (board[x] == board[i] || x - i == tmp)
        	return (0);
        i++;
     }
     return (1);
}

int	nqueen(int x)
{
	int		i;
    int		cnt;
    
    cnt = 0;
    i = 0;
	if (x == 10)
    {
    	cnt++;
        print...
        return (cnt);
    }
    while (i < 10)
    {
    	board[x] = i;
        if (judge(x, board))
        	nqueen(x + 1);
        i++;
    }
    return (cnt);
}

1.バックグラウンド追跡...

backtrackingはDFSに対する改良アルゴリズムである.
DFS:深度優先ナビゲーション
これはすべての方法に完全にナビゲートする方法です.
検索しないと正解にならない遡及により、検索効率が向上します!
=>>通常は「トリム」と呼ばれます.

ではDFSとは何でしょうか…?

ツリーまたはグラフィックでルートディレクトリを検索します.できるだけ深く見て、ない場合は他のルートディレクトリに戻って参照します.
再帰関数またはスタックを使用して実装します.
前のC問題では、再帰関数を使用したことがあると思います.
再帰関数を呼び出し、下部にwrite、putchar文を置き、最寄りから出力!!
差が少なくていいと思います!!
しかし、ここでは再帰関数を実行する条件を示します!

アクセスするグラフィック、ツリー、配列のデータ構造が作成されました.

まず、繰り返し文でインデックスを変更します.

インデックスにすでにアクセスしている場合は、アクセスしません.
(+dfs)

もう一つ条件を与えて、条件を満たさないと枝を切って入らない!
(+バックトレース)

単純なソースコードの例

出典:ウィキペディア(dfs)
注意:https://youtu.be/7C9RgOcvkvo

const int MAX = 100'001;

bool visited[MAX]; // 방문 배열. visited[node] = true이면 node는 방문이 끝난 상태이다.

void dfs(const vector<int> graph[], int current) { // graph는 인접 리스트, current는 현재 노드
    visited[current] = true; // current 방문

    for(int next: graph[current]) { // current의 인접 노드를 확인한다. 이 노드를 next라고 하자.
        if(!visited[next]) { // 만일 next에 방문하지 않았다면
            dfs(graph, next); // next 방문
        }
    }
}

/* ************************************************************************** */
/*                                                                            */
/*                                                        :::      ::::::::   */
/*   ft_ten_queens_puzzle.c                             :+:      :+:    :+:   */
/*                                                    +:+ +:+         +:+     */
/*   By: hyojeong <[email protected]>     +#+  +:+       +#+        */
/*                                                +#+#+#+#+#+   +#+           */
/*   Created: 2022/02/12 01:13:42 by hyojeong          #+#    #+#             */
/*   Updated: 2022/02/14 09:40:48 by hyojeong         ###   ########.fr       */
/*                                                                            */
/* ************************************************************************** */

#include <unistd.h>

# 먼저, 해당 위치에 퀸을 놓을 수 있을지 판단하는 judge 함수
# ==> 백트래킹에 해당하겠죠!!!
int	judge(int x, int board[])
{
	int		i;
	int		tmp;

	i = 0;
	while (i < x)
	{
		tmp = board[x] - board[i];
		if (tmp < 0)
			tmp *= -1;
		if (board[x] == board[i] || x - i == tmp)
			return (0);
		i++;
	}
	return (1);
}

# 단순히 보드를 프린트해주는, 프린트 보드 함수
void	print_board(int board[])
{
	int		index;
	char	tmp;

	index = 0;
	while (index < 10)
	{
		tmp = board[index] + 48;
		write(1, &tmp, 1);
		index++;
	}
	write(1, "\n", 1);
}

# 핵심. cnt의 값을 기록해주고, 해당 위치에 퀸을 놓을 수 있다면, 다음 열로 넘어가는, 재귀를 이용한 퀸 함수!
void	queen(int x, int *cnt, int board[])
{
	int		i;

	i = 0;
	if (x == 10)
	{
		*cnt = *cnt + 1;
		print_board(board);
		return ;
	}
	while (i < 10)
	{
		board[x] = i;
		if (judge(x, board))
			queen(x + 1, cnt, board);
		i++;
	}
}

# cnt를 반환시키는, 문제에서 구현하라는 프로토타입 함수
int	ft_ten_queens_puzzle(void)
{
	int		cnt;
	int		index;
	int		board[10];

	cnt = 0;
	index = 0;
	while (index < 10)
		board[index++] = 0;
	queen(0, &cnt, board);
	return (cnt);
}

潮流

まず、Boardに億円を充てる.

Quinn再帰関数を実行します.

2-0. どうしたんですか.なぜ(0,cnt,board)を使用して実行しますか?
インデックスのクイーンに入ることにします!!
2-1. quinn再帰関数ではboard[0]=0を入れて判断する.他の場所は皇后を埋め尽くしていないので、もちろん通過しました.
2-2. 次に、Boardの最初のインデックスにおけるQueenの位置を決定します.
しかし、この再帰関数は繰り返し文で実行され、以下にi++があるのではないでしょうか.
条件がそうであれば、また入って、そうでなければ、繰り返し文が再実行されます...
条件を満たすすべての皇后が出力され、個数が返されます.