八皇后问题 - 黑马程序员技术交流社区

import java.util.*;
/*
* 8皇后问题
* 步骤：
* 1. 用二维数组表示棋盘，i行j列为0，表示未放置皇后，为1表示已放置皇后
* 2. 对每一行，遍历各列，尝试放置皇后
* 3. 第i行j列放置完毕，递归放置之后的行列
* 4. 如果8行全部放置好皇后，输出这种摆法
*
*/
public class EightQueens {
public static final int QUEENS = 8;
public static void main(String[] args) {
// 棋盘定义为8行8列的二维数组
// 如果i行j列没有放置皇后，a[i][j] = 0;否则a[i][j]=1
int[][] board = int[QUEENS][QUEENS];
Arrays.fill(board, 0);
fillBoard(board, 0);
}
// fillBoard: 在棋盘board的第row行放置皇后
public static void fillBoard(int[][] board, int row) {
// 如果已放置的皇后数达到要求，则输出当前的棋盘状况
if (row == QUEENS - 1)
printBoard(board, QUEENS);
// 从列0到列8之中选一列放置皇后
for (int col = 0; col < QUEENS; i++) {
// 如果row行col列放置皇后与之前的皇后不冲突
if (canPlace(board, row, col) {
// 在row行col列放置皇后
board[row][col] = 1;
// 递归，以当前棋盘状况为基础，遍历row+1行到第8行放置皇后的所有方法
fillBoard(board, row + 1);
// 取消col列放置的皇后，继续for循环，准备在col+1列放置皇后
board[row][col] = 0;
}
}
}
// canPlace: 能否在row行col列放置皇后
public static boolean canPlace(int[][] board, int row, int col) {
// 从row-1行开始，检测每一行的皇后是否与row行col列的皇后冲突
for (int i = row - 1, colOffset = 1; i >= 0; i--, colOffset++) {
int aboveLeft = col - colOffset; // 左上对角线
int aboveRight = col + colOffset; // 右上对角线
if (board[i][col] == 1 // 不能与之前的皇后同列
||
// 左上对角线不能有皇后
aboveLeft >= 0 && board[i][aboveLeft] == 1
||
// 右上对角线不能有皇后
aboveRight < QUEENS && board[i][aboveRight] == 1)
return false;
}
return true;
}
// printBoard: 打印出八皇后在棋盘上的每一种摆法
public static void printBoard(int[][] board, int size) {
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
System.out.print(board[i][j] + " ");
System.out.println();
}
}
}

复制代码