Java算法五：八个皇后
八个皇后（Queen）
问题说明：
八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。
问题描述：
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n1×n1，而皇后个数也变成n2。而且仅当 n2 = 1 或 n1 ≥ 3 时问题有解。
结果：
Java代码：
|
package com.allen;
public class Queen { //同栏是否有皇后，1表示有 private int[] column; //右上至左下是否有皇后 private int[] rup; //左上至右下是否有皇后 private int[] lup; //解答 private int[] queen; //解答编号 private int num; public Queen(){ column=new int[8+1]; rup=new int[(2*8)+1]; lup=new int[(2*8)+1]; for(int i=1;i<=8;i++) column[i]=0; for(int i=1;i<=(2*8);i++) rup[i]=lup[i]=0; //初始定义全部无皇后
queen=new int[8+1]; }
public void backtrack(int i){ if(i>8){ showAnswer(); }else{ for(int j=1;j<=8;j++){ if((column[j]==0)&&(rup[i+j]==0)&&(lup[i-j+8]==0)){ //这里右上到左下是左边开始数的，并且是从2开始计数的总共8个正好到9，而左上到右下是做右边开始数的所以开头是8.明显是从1开始计数的。而循环是先循环行的， //所以每次只需要判断列上是否有皇后就行了。 //若无皇后 queen[i]=j; //设定为占用 column[j]=rup[i+j]=lup[i-j+8]=1; backtrack(i+1); //循环调用 column[j]=rup[i+j]=lup[i-j+8]=0; } } } }
protected void showAnswer(){ num++; System.out.println("\n解答"+num);
for(int y=1;y<=8;y++){ for(int x=1;x<=8;x++){ if(queen[y]==x){ System.out.print("Q"); }else{ System.out.print("."); } }
System.out.println(); } }
public static void main(String[]args){ Queen queen=new Queen(); queen.backtrack(1); } } |