关于算法:算法八皇后Java实现

40次阅读

共计 1032 个字符，预计需要花费 3 分钟才能阅读完成。

八皇后算法形容如下：
在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法！

上面来剖析一波，假如此时咱们想要在彩色方块地位搁置一个皇后：

如果一列一列的搁置皇后的话，图中彩色地位能搁置一个皇后的合法性条件为：
1、绿色线条通过的方格没有皇后（不处于同一斜线）
2、红色线条通过的方格没有皇后（不处于同一行）
3、紫色线条通过的方格没有皇后（不处于同一斜线）

也就是说如果以彩色方块地位为参照原点：（0,0）坐标点，紫色和绿色两个线条别离是斜率为 1 和 - 1 的两个函数，如下图：
紫色线所代表的函数是：y = -x;
绿色先所代表的函数是：y=x;
（横坐标是列，纵坐标为行，留神行从上到下递增）

但凡位于这两条函数线上的地位（点）以及横坐标（阐明位于同一行）都不能有皇后。也即行和列的差值要相等，如图所示

Java 代码实现：

public class EightQueenMain {private static int[] queen = new int[]{-1, -1, -1, -1, -1, -1, -1, -1};
  private static int count = 0;

  public static void main(String[] args) {eightQueue(0);
    System.out.println(count);
  }

  private static boolean isLegal(int currentRow, int currentCol) {for (int col = 0; col < currentCol; col++) {if (currentRow == queen[col]) { // 只判断行相等，因为是按列放皇后的
        return false;
      }
      if (Math.abs(queen[col] - currentRow) == Math.abs(col - currentCol)) {// 在斜线上 ( 行列差值相等)
        return false;
      }
    }
    return true;
  }

  private static void eightQueue(int currentCol) {for (int row = 0; row < 8; row++) {if (isLegal(row, currentCol)) {queen[currentCol] = row;
        if (currentCol == 7) { // 达到最初一列取得正确后果
          count++;
        }
        eightQueue(currentCol + 1);
      }
    }

  }
}