Java のエイトクイーンズプロブレム

Sheeraz Gul 2023年10月12日

Java Java Algorithm

このチュートリアルでは、Java の 8 クイーン問題について説明します。

Java のエイトクイーンズプロブレム

エイトクイーンの問題は、8 x 8 のチェス盤に 8つのクイーンを互いに攻撃しないように配置する必要があるということです。つまり、チェスではクイーンが移動できるため、同じ行、列、または対角線に 2つのクイーンを配置することはできません。

バックトラッキングは、Java のエイトクイーンまたは N クイーンの問題を解決するために使用できます。まず、バックトラッキングアルゴリズムについて説明します。

エイトクイーン問題にバックトラッキングアルゴリズムを使用する

バックトラッキングアルゴリズムを使用してエイトクイーン問題を解決するという考え方は、クイーンを左端の列から始めて異なる列に個別に配置することです。列にクイーンを配置し、以前に配置された他のクイーンとの衝突を確認します。

次に列で、行がクラッシュに含まれていない場合、列と行の両方をエイトクイーン問題の解決策の一部としてマークします。衝突していない状況が見つからない場合はバックトラックが使用され、false が返されます。

以下は、バックトラッキングアルゴリズムを使用してエイトクイーンズ問題を解決する段階的なプロセスです。

まずは一番左の列から。
すべてのクイーンが配置された場合にコードが true を返す条件を作成します。
次に、次の手順を実行して、列のすべての行を試します。
- クイーンが行に安全に配置されている場合、この行と列は、他のソリューションを再帰的にチェックするソリューションの一部としてマークされます。
- クイーンが安全に一列に配置されている場合は、true を返します。
- クイーンが安全に列に配置されていない場合は、行と列のマークを外し、ソリューションをバックトラックして、最初のオプションに戻り、ソリューションを他の行に適用します。
すべての行をチェックしても解決策がない場合は、false を返してバックトラッキングアルゴリズムをトリガーする必要があります。

上記の手順に基づいて例を実装してみましょう。

package delftstack;

public class EightQueen {
  // Size of the board should be 8x8 for the eight queens problem
  public static final int SIZE_OF_BOARD = 8;

  boolean[][] BOARD_BOOLEAN;
  // For an empty place
  public static final boolean EMPTY_PLACE = false;
  // For a place that contains a queen
  public static final boolean QUEEN_PLACE = true;
  // The number of moves
  public static final int MOVES_NUMBER = 4;
  // The horizontal moves
  int[] Horizontal_Moves;
  // The Vertical moves
  int[] Vertical_Moves;

  public int Queens = 0;

  public EightQueen() {
    // Constructor creates an empty board
    BOARD_BOOLEAN = new boolean[SIZE_OF_BOARD][SIZE_OF_BOARD];
    for (int row = 0; row < BOARD_BOOLEAN.length; row++) {
      for (int col = 0; col < BOARD_BOOLEAN[row].length; col++) {
        BOARD_BOOLEAN[row][col] = EMPTY_PLACE;
      }
    }

    Horizontal_Moves = new int[MOVES_NUMBER];
    Vertical_Moves = new int[MOVES_NUMBER];
    // move up right
    Horizontal_Moves[0] = -1;
    Vertical_Moves[0] = 1;
    // move down left
    Horizontal_Moves[1] = 1;
    Vertical_Moves[1] = -1;
    // move up left
    Horizontal_Moves[2] = -1;
    Vertical_Moves[2] = -1;
    // move down right
    Horizontal_Moves[3] = 1;
    Vertical_Moves[3] = 1;
  }

  public boolean Queens_Placing(int Board_Column) {
    if (Board_Column >= SIZE_OF_BOARD) {
      return true;
    } else {
      boolean Queen_Placed = false;
      int Board_Row = 0;

      while (!Queen_Placed && Board_Row < SIZE_OF_BOARD) {
        if (Queen_UnderAttack(Board_Row, Board_Column)) {
          ++Board_Row;
        } else {
          Set_Queen(Board_Row, Board_Column);
          Queen_Placed = Queens_Placing(Board_Column + 1);
          if (!Queen_Placed) {
            Remove_Queen(Board_Row, Board_Column);
            ++Board_Row;
          }
        }
      }
      return Queen_Placed;
    }
  }

  private void Remove_Queen(int Board_Row, int Board_Column) {
    BOARD_BOOLEAN[Board_Row][Board_Column] = EMPTY_PLACE;
    // Remove the comment from the code below to check which place the queen was removed.
    // System.out.printf("The queen is REMOVED from [%d][%d]\n", Board_Row, Board_Column);
    --Queens;
  }

  private void Set_Queen(int Board_Row, int Board_Column) {
    BOARD_BOOLEAN[Board_Row][Board_Column] = QUEEN_PLACE;
    // Remove the comments from the code below to check where the queen was placed
    // System.out.printf("The queen is PLACED in [%d][%d]\n", Board_Row, Board_Column);
    ++Queens;
  }

  public boolean Queen_UnderAttack(int Board_Row, int Board_Column) {
    boolean Queen_Condition = false;
    // check the row
    for (int Column = 0; Column < SIZE_OF_BOARD; Column++) {
      if ((BOARD_BOOLEAN[Board_Row][Column] == true)) {
        Queen_Condition = true;
      }
    }

    // check the column
    for (int Row = 0; Row < BOARD_BOOLEAN.length; Row++) {
      if (BOARD_BOOLEAN[Row][Board_Column] == true) {
        Queen_Condition = true;
      }
    }

    // check the diagonal
    for (int Row = Board_Row, Column = Board_Column; Row >= 0 && Column < 8;
         Row += Horizontal_Moves[0], Column += Vertical_Moves[0]) {
      if (BOARD_BOOLEAN[Row][Column] == true) {
        Queen_Condition = true;
      }
    }
    for (int Row = Board_Row, Column = Board_Column; Row < 8 && Column >= 0;
         Row += Horizontal_Moves[1], Column += Vertical_Moves[1]) {
      if (BOARD_BOOLEAN[Row][Column] == true) {
        Queen_Condition = true;
      }
    }
    for (int Row = Board_Row, Column = Board_Column; Row >= 0 && Column >= 0;
         Row += Horizontal_Moves[2], Column += Vertical_Moves[2]) {
      if (BOARD_BOOLEAN[Row][Column] == true) {
        Queen_Condition = true;
      }
    }
    for (int Row = Board_Row, Column = Board_Column; Row < 8 && Column < 8;
         Row += Horizontal_Moves[3], Column += Vertical_Moves[3]) {
      if (BOARD_BOOLEAN[Row][Column] == true) {
        Queen_Condition = true;
      }
    }

    return Queen_Condition;
  }

  public void Display_Board() {
    int Count = 0;
    for (int Board_Row = 0; Board_Row < BOARD_BOOLEAN.length; Board_Row++) {
      for (int Board_Column = 0; Board_Column < BOARD_BOOLEAN[Board_Row].length; Board_Column++) {
        if (BOARD_BOOLEAN[Board_Row][Board_Column] == true) {
          System.out.printf("|%s| ", " Q ");
          Count++;
        } else {
          System.out.printf("|%s| ", " X ");
        }
      }
      System.out.println();
    }

    System.out.printf("%d queens problem is solved, the queens are placed.\n", Count);
  }

  public static void main(String[] arg) {
    EightQueen EightQueen_Problem = new EightQueen();
    EightQueen_Problem.Queens_Placing(0);
    EightQueen_Problem.Display_Board();
  }
}

上記のコードは、バックトラッキングアルゴリズムソリューションを使用してエイトクイーン問題を実装します。お互いを殺すことができない場所に女王を配置します。

Q がクイーンを表す出力を参照してください。

| Q | | X | | X | | X | | X | | X | | X | | X |
| X | | X | | X | | X | | X | | X | | Q | | X |
| X | | X | | X | | X | | Q | | X | | X | | X |
| X | | X | | X | | X | | X | | X | | X | | Q |
| X | | Q | | X | | X | | X | | X | | X | | X |
| X | | X | | X | | Q | | X | | X | | X | | X |
| X | | X | | X | | X | | X | | Q | | X | | X |
| X | | X | | Q | | X | | X | | X | | X | | X |
8 queens problem is solved, the queens are placed.

上記のアルゴリズムの時間計算量は O(N!) で、補助空間は O(N2) です。

著者： Sheeraz Gul

Sheeraz is a Doctorate fellow in Computer Science at Northwestern Polytechnical University, Xian, China. He has 7 years of Software Development experience in AI, Web, Database, and Desktop technologies. He writes tutorials in Java, PHP, Python, GoLang, R, etc., to help beginners learn the field of Computer Science.

LinkedIn Facebook

Java のエイト クイーンズ プロブレム

エイト クイーン問題にバック トラッキング アルゴリズムを使用する

関連記事 - Java Algorithm

Java のエイトクイーンズプロブレム

エイトクイーン問題にバックトラッキングアルゴリズムを使用する