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軸はそれぞれ同じ数移動した.
最適化
いつも足りない.コードをより簡潔に記述し,演算量をさらに減らす必要がある.
時間の複雑さを考慮したコードの作成を練習する.
Reference
この問題について(N-Queen), 我々は、より多くの情報をここで見つけました https://velog.io/@bty5596/N-Queenテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol