赞
踩
下面我们来用代码完成八皇后问题:
public class EightQueen { private static int count; public static void main(String[] args) { int[][] chessboard = newChessboard(); go(chessboard,0); } private static void print(int[][] chessboard) { for (int i = 0; i < chessboard.length; i++) { for (int j = 0; j < chessboard[i].length; j++){ System.out.print(chessboard[i][j] + " "); } System.out.println(); } } /** * 开始摆放 * @param chessboard n表示第几个皇后 */ private static void go(int[][] chessboard, int n) { // 判断棋盘是否摆完皇后 if (n == 8) { // 输出数组 System.out.println("第"+(++count)+"种解法:"); print(chessboard); // 1中摆法结束,初始化数组 return; } // 第i行没有摆放皇后,我们可以摆皇后,我们先摆在这行的第一列 for (int j = 0; j < chessboard[n].length; j++) { // 开始摆皇后之前,把之前该行摆的清零 for (int t = 0; t < chessboard[n].length; t++) { chessboard[n][t] = 0; } // 判断是否和前面已摆的皇后是否冲突,不冲突就继续下一行 if (!isConflict(n,j,chessboard)) { chessboard[n][j] = 1; go(chessboard, n+1); } // 冲突就继续这一行的下一列 } } /** * 判断第i行第j列的皇后与其他皇后是否冲突, * @param i * @param j * @param chessboard * @return */ private static boolean isConflict(int i, int j, int[][] chessboard) { if (i == 0) { return false; } for (int m = 0; m < i; m++) { // 判断同一列是否有别的皇后 if (chessboard[m][j] == 1){ return true; } // 判断同一条斜线 if (j-(i-m) >= 0 && chessboard[m][j - (i-m)] == 1) { return true; } if (j + (i-m) < chessboard[m].length && chessboard[m][j + (i-m)] == 1) { return true; } } return false; } /** * 创建八皇后棋盘 * @return */ private static int[][] newChessboard() { int[][] chessboard = new int[8][8]; return chessboard; } }
输出结果:
...... ...... 第89种解法: 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 第90种解法: 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 第91种解法: 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 第92种解法: 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0
从结果可以看出一共有92种解法。代码注释详细,不做过多解释
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。