エイトクイーン問題C ++再帰

Eight Queens Problem C Recursion

最近、再帰を確認し、再テストの準備をしていました。エイトクイーンの問題を見たところです。

主なアイデアは、8 * 8のチェス盤を描くことです。クイーンの位置は、0に設定できます。それ以外の場合は、1です。正しい解は各行のクイーンでなければならないため、問題は行の深さ優先探索によって分解されます。 （0,0）からクイーンを配置し、次の行で最初の0を検索し、クイーンを配置し、対応する配置不可能な位置を1に設定してから、次の行で最初の0を検索します... 7行目の最初の0に遭遇します（最初の開始から0行目）クイーンを配置するために利用できる0がまだある場合、解決策が見つかります。それ以外の場合は、前の行に戻り、チェス盤を復元し、2番目の0を見つけます。女王を配置するための行、そして下に検索を続けます。複数のリターンの後、行のすべての0も検索が完了した後、同様の検索のために前の行に戻ります。

発生する問題は主に2つの側面にあります。

1.ループして、クイーンが対応する正方形を設定する操作を実現します。ループ状態に注意し、4つの状況を考慮してください。

2.再帰的にロジックをループします。コードコメントを参照してください。

さらに、再帰の開始位置が指定されているため（0,0）、0行目のすべての位置に対して再帰的な解を実現するには、main関数をループする必要があります。この点も長い間見られていましたが、再帰的な層の数を数えることによってのみわかりました。

#include #include using namespace std //The Eight Queens Question int table[8][8] = {} int count = 0 typedef enum arg {CLR,SET} ctr int countdg//recursive layer count void SetRowLineDiag(int x,int y,ctr arg) void EightQ(int x,int y) void copyArray(int (*array_temp)[8],int (*table)[8]) //Array pointer void coutArray(int (*array)[8]) int main() { int i int array_temp[8][8]={} copyArray(array_temp,table) for(i=0i<8i++) { copyArray(table,array_temp) //Pay attention to the restoration of the board after returning EightQ(0,i) } cout<=s-7i--) { j=s-i table[i][j] = arg } } else if(s<7) { for(j=0j=y)//right slash { for(i=x-y,j=0i<=7i++,j++) table[i][j] = arg } else { for(j=y-x,i=0j<=7i++,j++) table[i][j] = arg } } void copyArray(int (*array_temp)[8],int (*table)[8]) //Array pointer { int i,j for(i=0i<8i++) { for(j=0j<8j++) array_temp[i][j] = table[i][j] } } void coutArray(int (*array)[8])//output chess board { int i,j for(i=0i<8i++) { for(j=0j<8j++) cout<
解決した92のソリューション