問題の説明: 図に示すように、チェス盤上に 8 つのクイーンを配置します。2 つのクイーンは互いに攻撃できません (つまり、2 つのクイーンは同じ行、列、または対角線上にありません)。
この記事では、2 つの問題に対してわずかに異なる解決策が使用されますが、どちらも 1 次元配列を使用します。 6.20 では、8 つの要素を含む 1 ビットの配列を確立し、6.22 では配列の値をランダムにシャッフルし、その値を添え字と比較する必要がありました。必須です すべて検索効果的なレイアウト。ここでは 8 進数を使用し、001234567 から 076543210 までのすべての数値を走査し、8 進数の文字列に変換し、各ビットを添え字と比較して、条件を満たすレイアウトを出力します。実装原理と方法については、以下で詳しく紹介します。
その1 正しいレイアウトかどうかの判断方法
チェス盤を 0 ～ 7 の範囲の 8*8 行列として扱います。左側の図を観察すると、そのレイアウトが一連の数字のペア (上から下へ)、つまり (0, 0)、(1, 6)、(2, 3)、(3) で表されることがわかります。 、5)、(4、7)、(5、1)、(6、4)、(7、2)。配列で表されます。つまり、 int []list = {0, 6, 3, 5, 7, 1, 4, 2};
明らかに、これは有効なレイアウトです。次に、効果的なレイアウトでは、添え字と配列内のそれに対応する値、つまり i と list[i] の間に何らかの関係があるでしょうか?
ここでは list[i] = k; list[j] = q; (i > j) と設定します (紙に描くと理解しやすいです)。
1. k != q;
2. i - j == k - q または i - j == q -k (質問から得られます)
k != q であることを保証するために、ここで配列リストが宣言され、list[i] = i になるように初期化されます。 次に、配列をランダムにシャッフルし、条件 2 が満たされるかどうかを確認します。
次のようにコードをコピーします。
//配列を作成して初期化する
int [] リスト = 新しい int [arrSize];
for(int i = 0; i < arrSize; i++)
リスト[i] = i;
// 配列をランダムにシャッフルする
public static voidrandomizeArray(int [] list){
int arrSize = list.length;
int ranIndex;
for(int i = 0; i < arrSize; i++){
ranIndex = (int)(Math.random() * arrSize);
if(ranIndex != i){
int temp = リスト[i];
リスト[i] = リスト[ranIndex];
リスト[ranIndex] = 一時;
}
}
}
6.20のコード本体は以下の通り
次のようにコードをコピーします。
// 6.20 ゲーム: エイトクイーンズ
public voidsolveEightQueens(){
int arrSize = 8;
int [] リスト = 新しい int [arrSize];
for(int i = 0; i < arrSize; i++)
リスト[i] = i;
int カウント = 0;
ブール値 notValid = true;
while(notValid){
カウント++;
notValid = false;
ランダム化配列(リスト);
for(int i = 0; i < arrSize; i++){
for(int j = i + 1; j < arrSize; j++){
if(j - i == Math.abs(list[j] - list[i])){ // 条件が満たされているかどうかを確認します
notValid = true;
壊す;
}
}
if(notValid) ブレーク;
} // 外側の for ループの終わり
} // これで終わり
// 結果を出力する
int i;
System.out.println("O(∩_∩)あはは～、「 + count + " 回試しましたが、最終的には成功しました。」);
for(i = 0; i < arrSize - 1; i++){
System.out.print("(" + i + ", " + list[i] + "), ");
}
System.out.println("(" + i + ", " + list[i] + ")");
}
パート 2 有効なレイアウトをすべて検索する
6.22 では、有効な 8 クイーン レイアウトをすべて見つける必要があるため、配列をランダムにシャッフルする方法は適用できなくなり、可能なすべての配列を走査できる方法を見つける必要があります。最も直接的な方法としては、8層のforループを使う方法がありますが、コード量が多すぎて頭がくらくらしやすいため、この方法は使用しません。
パート 1 の配列の値を注意深く観察すると、それらはすべて 0 ～ 7 の範囲にあることがわかります。そのため、8 進整数を使用して走査することで、すべての順列が確実に含まれるようにすることができます。 8 桁の数値が異なるため、8! = 40320 通りの置換が可能で、8 進数の合計数は 8^8 = 16777216 となるため、可能な比率は 40320/16777216 = 1/416 となり、結果は 40320 になります。順列 最終的な有効なレイアウトを除外するためのチェックもあります。この方法はまだ少し非効率的ですが、より効率的な方法はまだ見つけていません。
次のようにコードをコピーします。
// 6.22 ゲーム: 8 つのクイーン問題に対するさまざまな解決策 (int 値をインクリメントし、それを 8 進数の文字列に変換し、チェックする)
public static voidsolveEightQueensMethod(){
int start = 001234567; // 8 進数
int end = 076543210;
int count = 0; // 有効なレイアウトの数を計算します。
for(int i = 開始; i < 終了; i++){
ブール値 isValid = isValid(i);
if(isValid){
if(++カウント % 7 == 0)
System.out.println(Integer.toOctalString(i) + ": " + isValid);
else System.out.print(Integer.toOctalString(i) + ": " + isValid + " ");
}
}
System.out.println("count = " + count); // 有効なレイアウトの数を出力します。
}
// 数値が有効なレイアウトかどうかを確認します
パブリック静的ブール値 isValid(int 数値){
String numOct = Integer.toOctalString(数値);
int arrSize = numOct.length();
if(arrSize==7) { // 数値の最初の桁が 0 の場合、生成される文字列は 7 文字のみです
numOct = '0' + numOct;
arrSize++;
}
for(int i = 1; i < arrSize; i ++){
for(int j = i - 1; j >= 0; j--){
if(numOct.charAt(i) == numOct.charAt(j)) return false; // 同じ列
if(i - j == Math.abs(numOct.charAt(i) - numOct.charAt(j))) return false; //同じ対角線
}
}
true を返します。
}
パート 3 拡張: 組み合わせの生成の問題
去年の筆記試験でこんな問題がありました。シーケンスを指定して、すべての組み合わせを出力します。例えば、
「123」の出力：1、2、3、12、13、21、23、31、32、123、132、213、231、312、321
「abcd」の出力: a、b、c、d、ab、ac、ad、ba、bc、bd、ca、cb、cd、da、db、dc、abc、acb、abd、adb、acd、adc、 ...、abcd、...
6.22 では、8 クイーン レイアウトをすべて見つけるために使用される方法は、int 型の番号をインクリメントし、1 つずつチェックすることです。上記の問題も同様の方法で解決できます。ただし、効率は少し悪いので、より効率的な方法がある場合は専門家に相談してください。