N-Queen



これは典型的な遡及問題で、正解だと思います.
大衆的な解答より、もっと複雑に解答します.
チェス盤では、1列目から順にクイーンズエリアを埋め尽くす.
女王がこの位置の横、縦、対角線にいることを確保し、彼女がいないとき、
方法は同じです.
これをコードとして実装する場合,少し複雑に記述される.

マイコード

#include <iostream>

using namespace std;

int n, answer = 0;
int visited[16][16] = { 0, };

bool noUpDiag(int i, int num)
{
	if (i - 1 < 0 || num - 1 < 0)
		return true;

	if (visited[i - 1][num - 1])
		return false;

	return noUpDiag(i - 1, num - 1);
}

bool noDownDiag(int i, int num)
{
	if (i + 1 >= n || num - 1 < 0)
		return true;

	if (visited[i + 1][num - 1])
		return false;

	return noDownDiag(i + 1, num - 1);
}

bool noRow(int i, int num)
{
	if (num - 1 < 0)
		return true;

	if (visited[i][num - 1])
		return false;

	return noRow(i, num - 1);
}

void queen(int num)
{
	if (num == n)
	{
		answer++;
		return;
	}

	for (int i = 0; i < n; i++)
	{
		if (noUpDiag(i, num) && noDownDiag(i, num) && noRow(i, num))
		{
			visited[i][num] = 1;
			queen(num + 1);
			visited[i][num] = 0;
		}
	}

}




int main()
{
	
	cin >> n;

	queen(0);

	cout << answer;
}
今はおもしろいですね.
まず、このコードは2 Dアクセス配列を宣言し、アクセスするかどうかを確認します.
(私もなぜか分かりませんが)
左上、左下、横に皇后がいるかどうか.
関数をそれぞれ宣言し、再帰的に表します.
そうする必要はありません.
1次元配列を宣言するだけで、すべてを表現することができます.

単純コード

#include <iostream>
#include <algorithm>

using namespace std;

int n, answer = 0;
int board[16] = { 0, };

bool isPossible(int position)
{
	for (int i = 0; i < position; i++)
	{
		if(board[position] == board[i] || abs(board[position] - board[i]) == abs(position - i))
			return false;
	}

	return true;
}

void queen(int size)
{
	if (size == n)
	{
		answer++;
		return;
	}

	for (int i = 0; i < n; i++)
	{
		board[size] = i;

		if (isPossible(size))
			queen(size + 1);
	}

}

int main()
{
	cin >> n;

	queen(0);

	cout << answer;
}
1 Dプレートアレイ、
Qeenをその位置に配置できるかどうかを決定するにはisPosible()関数を1つだけ必要とします.
実現できる.
配列インデックスを考慮すると,チェス盤は0行0列から始まる.
board[1]=2と言えば=>2行目1列、
bord[3]=4=>4行3列で、以下のようになります.
board配列の値を行に、インデックスを列に指定できます.
2人の皇后が対角線にいたら
2つの皇后の各行、10座標の差は同じです.
ある点から対角線に移動
x軸のため、y軸はそれぞれ同じ数移動した.

最適化


いつも足りない.コードをより簡潔に記述し,演算量をさらに減らす必要がある.
時間の複雑さを考慮したコードの作成を練習する.