Java 八皇后问题解释

Python014

Java 八皇后问题解释,第1张

public class Queen{//同栏是否有皇后,1表示有private int[] column//右上至左下是否有皇后private int[] rup//左上至右下是否有皇后private int[] lup//解答private int[] queen//解答编号private int numpublic Queen(){column=new int[8+1]rup=new int[(2*8)+1]lup=new int[(2*8)+1]for(int i=1i<=8i++)column[i]=0for(int i=1i<=(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=1j<=8j++){if((column[j]==0)&&(rup[i+j]==0)&&(lup[i-j+8]==0)){//若无皇后queen[i]=j//设定为占用column[j]=rup[i+j]=lup[i-j+8]=1backtrack(i+1) //循环调用column[j]=rup[i+j]=lup[i-j+8]=0}}}} protected void showAnswer(){num++System.out.println("\n解答"+num)for(int y=1y<=8y++){for(int x=1x<=8x++){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)}}

递归

首先每一行放置均会循环,也就是每一行的皇后都会被依次放置在8个位置上;

1)第一行在第一个位置上放置1枚皇后;

2)第二行在第一个位置上放置皇后,如果与已有的皇后不在一条直线上,则进入下一行,否则位置+1

3)余下几行均依照步骤2)的方法进行放置,当最后一行放置好,打印输出;

可以写个函数,EightQueen(int

n,

int

*Pos),其中n表示第几行,Pos指向一个数组,Pos[i]=j表示第i行的位置是j;EightQueen(int

n,

int

*Pos)从n=1开始递归,到n=8递归结束。

代码就不写了,没写过java,写不来

希望我解释的你能明白:

把棋盘看成二维方阵,行从上到下编号0-7(就是i),列从左到右编号0-7(就是j),这样棋盘上每个点都可以表示为(i,j)

从键盘的右上角(0,7)到左下角(7,0)的对角线,以及这条线的平行线,就是反对角线,也就是这个程序里的undiagonal。显然这个反对角线上任意2点(i1,j1)和(i2,j2)都满足i1+j1=i2+j2.因为i+j可能的取值范围是从0到14,所以把这个数组的长度定义为16(事实上15就可以了)

从键盘的左上角(0,0)到右下角(7,7)的对角线以及平行线,就是对角线,就是diagonal。同理,这个对角线及其平行线上任意2点都满足i1-i2=j1-j2.i-j的范围是-7到7,为了避免出现负数,程序里在这里+7,也是一个长度为16的数组(还是15就够了)

程序一开始的时候,i=j=0,所有的安全标识都是true,所以(0,0)这个点会被输出。这时,把diagonal【7】置为false。因为(1,1),(2,2)等等这些点都和(0,0)在一条对角线上(因为0-0+7=1-1+7=2-2+7),所以把这些点的对应的diagonal都置为false,也就是把diagonal【7】置为false

并且把undiagonal【0】也置为false,但是因为undiagonal【0】对应的元素只有(0,0)(因为只有0+0=0),所以这个对这一步没什么影响。

然后一点点递推,回溯,步骤就是这样。希望你看得懂,如果不明白的话给我发消息吧