實作_八皇后問題(n個)

EightQueensPuzzleV2.java

import java.util.Arrays;

/*
 * 八皇后問題(n個)
 * 此程式用來描述 回溯法(backtracking)
 * 根據上一版本進行修改
 * https://gist.github.com/lya79/6f51a1a6834229db172ccaaeedc0f888
 */
public class EightQueensPuzzleV2 {

  private int total = 8;//皇后數量
  private int[] result = new int[total];
  private int count = 0;

  public EightQueensPuzzleV2() {
    for (int column = 0; column < total; column++) {
      result[0] = column;
      nextRow(1);
    }
    System.out.println("總共: " + count + "個解");
  }

  public static void main(String[] args) {
    new EightQueensPuzzleV2();
  }

  private void print() {
    System.out.println(Arrays.toString(result));
    for (int row = 0; row < result.length; row++) {
      for (int column = 0; column < result.length; column++) {
        if (result[row] == column) {
          System.out.print("⚫");
        } else {
          System.out.print("⎕");
        }
        if (column < result.length - 1) {
          System.out.print("");
        }
      }
      System.out.println("");
    }
    System.out.println();
  }

  private void nextRow(int row) {
    for (int column = 0; column < total; column++) {
      result[row] = column;
      if (isError(row)) {
        continue;
      }
      if (row == total - 1) {
        print();
        count += 1;
        continue;
      }
      if (row < total - 1) {
        nextRow(row + 1);
      }
    }
  }

  private boolean isError(int row) {
    boolean error = false;
    for (int i = 0; i < row; i++) {
      int row2 = result[i];
      int row3 = result[row];
      int space = row - i;
      if (row2 == row3) {
        error = true;
      } else if (row2 == row3 + space) {
        error = true;
      } else if (row2 == row3 - space) {
        error = true;
      }
      if (error) {
        break;
      }
    }
    return error;
  }
}