Javaを使用する8人の女王

次のコードはうまく機能しますが、時間がかかりすぎます。 placeQueensにも多くの時間がかかります。プログラムには5〜10秒かかります。

public class EightQueen { public static void startSimulation(){ long startTime = System.currentTimeMillis(); char[] board; // Create an array // Repeat while queens are attacking do { // Generate a board board = getNewBoard(); // Place eight queens placeQueens(board); } while (isAttacking(board)); // Display solution print(board); long endTime = System.currentTimeMillis(); System.out.println(endTime - startTime); } /** placeQueens randomly places eight queens on the board*/ public static void placeQueens(char[] board) { int location; for (int i = 0; i < 8; i++) { do { location = placeQueens(); } while (isOccupied(board[location])); board[location] = "Q"; } } /** placeQueens randomly places one queen on the board */ public static int placeQueens() { return (int)(Math.random() * 64); } /** isAttacking returns true if two queens are attacking each other */ public static boolean isAttacking(char[] board) { return isSameRow(board) || isSameColumn(board) || isSameDiagonal(board); } /** isSameRow returns true if two queens are in the same row */ public static boolean isSameRow(char[] board) { int[] rows = new int[8]; for (int i = 0; i < board.length; i++) { if (isOccupied(board[i])) { rows[getRow(i)]++; } if (rows[getRow(i)] > 1) return true; } return false; } /** isSameColumn returns true if two queens are in the same column */ public static boolean isSameColumn(char[] board) { int[] columns = new int[8]; for (int i = 0; i < board.length; i++) { if (isOccupied(board[i])) { columns[getColumn(i)]++; } if (columns[getColumn(i)] > 1) return true; } return false; } /** isSameDiagonal returns true if two queens are on the same diagonal */ public static boolean isSameDiagonal(char[] board) { for (int i = 0; i < board.length; i++) { if (isOccupied(board[i])) { for (int j = 0; j < board.length; j++) { if (isOccupied(board[j]) && Math.abs(getColumn(j) - getColumn(i)) == Math.abs(getRow(j) - getRow(i)) && j != i) { return true; } } } } return false; } /** isOccupied returns true if the element in x is the char Q */ public static boolean isOccupied(char x) { return x == "Q"; } /** getNewBoard returns a char array filled with blank space */ public static char[] getNewBoard() { char[] board = new char[64]; for (int i = 0; i < board.length; i++) board[i] = " "; return board; } /** print displays the board */ public static void print(char[] board) { for (int i = 0; i < board.length; i++) { System.out.print( "|" + ((getRow(i + 1) == 0) ? board[i] + "|\n" : board[i])); } } /** getRow returns the row number that corresponds to the given index */ public static int getRow(int index) { return index % 8; } /** getColumn returns the column number that corresponds to the given index */ public static int getColumn(int index) { return index / 8; } } 

コメント

  • 検索方法を使用できる可能性がありますバックトラックあり。最初のフリー(占有されておらず、攻撃されていない)位置を選択するたびに、クイーンを1つずつ配置することを繰り返します。 n 番目の女王の自由な位置がない場合は、一歩下がって女王を移動します。 ( n -1)現在の場所から次の空き位置まで。 'に空き位置がない場合は、( n -1)を削除して、もう一度戻ります。空のボードに戻った場合、クイーンの配置は不可能です。 '戻る'ステップでクイーン( n -1)を正常に移動した場合は、配置を続行します n 番目のもの。ランダムな配置は効果がありません。
  • 'のmain()関数はどこにありますか?
  • @CiaPanに感謝しますが、もっと良い解決策があると思います。
  • @TobySpeightは、クラスをmain() !!
  • あなたに呼び出すだけです。クラスを呼び出すことはできません'クラスのインスタンスを作成するか、その静的メソッドを呼び出すことができます。 startSimulation()が主な機能になるはずですか?その場合は、代わりにmain()と呼ぶことができます。

回答

bogosort と同じように、高速な並べ替えアルゴリズムになることはありません。 「ボードを捨てて、N個の新しいクイーンをランダムに配置する」ソリューションは、5〜10秒よりも実際に速くなることはありません。

それでも、実際にある程度一貫してソリューションが見つかるのを見て嬉しく思いました。また、質問自体もうまく構成されているので、答える価値があると思います。

コメントですでに提案されているCiaPanのように、n-queensの問題を解決するためのはるかに優れた方法はバックトラックです。このアプローチを使用した私のクイックテストプログラムは、1ミリ秒(またはそれ以下)で8クイーンを解決します。 (そして、50ミリ秒で20クイーン)

ただし、「リセットしてランダムにn個の新しいクイーンを配置する」アプローチは興味深いので、1つの大きな改善を追加して、

/** placeQueens randomly places eight queens on the board*/ public static void placeQueens(char[] board) { int location; for (int i = 0; i < 8; i++) { do { location = placeQueens(i); } while (isOccupied(board[location])); board[location] = "Q"; } } /** placeQueens randomly places one queen on the board */ public static int placeQueens(int row) { return row * 8 + (int)(Math.random() * 8); } 

ここでのこの小さな変更により、解決までの時間が一貫して100ミリ秒未満になりました。なぜですか?これにより、検索スペースがO(n³)から減少するためです。 to O(n²)。これが機能する理由は、すべてのソリューションで各行に1つのクイーンが存在するためです。したがって、ボード全体ではなく、各行にランダムに1つ生成します。

コメント

  • すばらしい回答をありがとうございますが、'はすでに高速で終了したようですが、ランダムクイーンの設定に問題があります。
  • 検討する価値のある別のポイントがあります。@ IbrahimAliは'実際に彼の目的が何であるかを言わず、任意の有効な取り決めを見つけるかエイトクイーンのすべての有効な配置。ループで囲まれた体系的な検索で後者が実行されます(retur n考えられるすべての解決策、およびそれぞれが1回だけ)、ランダム生成はできません(答えを繰り返す可能性があり、すべての可能性が見つかったかどうかはわかりません。 RNGの品質が低いと、いくつかを見つけることができない場合もあります。
  • @CiaPan I ' m iv id = nブール値の “9a5035c1fb”>

位置単純にブール配列を作成し、ランダムに依存して'インデックスを使用しますクイーン、生成されたすべてのクイーンは、ブール配列で不正なインデックスをfalseに設定します。これは非常に時間がかかります。

  • @Imusあなたは'を必要としませんdo – whileループ。for (int i = 0; i < 8; i++)ループによって呼び出される各placeQueens(i)は、個別の行に位置を割り当てます。したがって、衝突は不可能であり、それらのテストは時間の無駄です。
  • ああ本当のCiaPan。よく発見されました。元のコードの各行に1つずつ生成するために、最小限の変更のみを行いました。そのため、'そのiをメソッドに渡しました。また、冗長なチェックに気づきましたが、解決策を見つけるのに1ミリ秒もかかりません。したがって、'とにかく違いを実際に伝えることはできません。
  • コメントを残す

    メールアドレスが公開されることはありません。 * が付いている欄は必須項目です