八皇后问题，一个古老而著名的问题，是回溯算法的典型案例。该问题由国际西洋棋棋手马克斯·贝瑟尔于 1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有 76 种方案。1854 年在柏林的象棋杂志上不同的作者发表了 40 种不同的解，后来有人用图论的方法解出 92 种结果。计算机发明后，有多种计算机语言可以编程解决此问题。
思路：函数
咱们的思路是程序要包含三个方法：1.主方法 2.判断方法1 3.判断方法2 4.输出方法code
首先说判断方法2，判断方法2的做用是判断该位置的皇后是否合法。本文采用以行的方法，一行一行赋值。因此该方法将当前的列位置与以前存在的皇后的位置进行比较判断并返回true or false。
判断条件有三个：
1.不与以前的皇后同列：从第一个皇后到当前皇后的前一个皇后，循环判断皇后的位置是否与当前的列位置相同，相同返回false。博客
//j为当前判断的列
//判断是否与以前的那些皇后在一个列
//一直寻找到第k-1个皇后，即上一个皇后
for(int i=0;i<k;i++)
{
if(index[i]==j)
{
return false;
}
}
2.不在以前的皇后的左下斜线上：首先要从当前皇后的前一个皇后判断，若是该位置在前一个皇后的左斜线上class
则该列位置+1等于前一个皇后的位置（列）；以此类推，以后判断前皇后的前一个皇后，记为前前皇后，若是在前前一个皇后的左斜线上，即该列位置+2等于前前一个皇后的位置（列）。变量
//判断当前列是否在上一个皇后的右下斜线上；
// k为当前寻找的皇后，故上一个皇后为k-1
//xo
//ox
//此时当前列向前一列就会和上一个八皇后的列位置相同
//xoo
//ooo
//oox
//此时需向前两列去比较上上一个八皇后
for (int lie=j-1,hang=k-1;lie>=0&&hang>=0;lie--,hang-- )
{
if(index[hang]==lie) {
return false;
}
}
3.不在以前的皇后的右下斜线上：与以前的同理，首先要从当前皇后的前一个皇后判断，若是该位置在前一个皇后的右斜线上。则该列位置-1等于前一个皇后的位置（列）；以此类推，以后判断前皇后的前一个皇后，记为前前皇后，若是在前前一个皇后的左斜线上，即该列位置-2等于前前一个皇后的位置（列）。搜索
//判断当前列是否在上一个皇后的右下斜线上；
//ox
//xo
//当前列向后一列，就会与上一个皇后相的列数相等
for (int lie=j+1,hang=k-1;lie>=0&&hang>=0;lie++,hang-- )
{
if(index[hang]==lie)
{
return false;
}
}
其次说判断方法1，该方法的目的是从第j列到最后一列进行查找，将每一列传入判断放法2，若是返回结果为true则将该列返回。该方法值得一提的是j列并不是全部的都是从头开始去查找，由于该问题涉及回溯，好比可能会查找到的皇后位置有误，即没有一列知足要求，此时须要回溯上一个皇后的位置。因此这里的j须要分状况讨论。该方法须要传入当前正在查找的皇后，而后判断该皇后的位置是-1仍是有具体位置，若是有具体位置则表明是回溯到这个皇后的，说明存的位置有误，须要从这个位置以后的位置继续查找新的位置，若是为-1，则说明为未查找过的，因此从头开始查找便可。代码以下：index为存放各个皇后位置的数组，index的下表表明行，数值表明列，好比index【0】=1，表明第一个皇后的位置为第一行第二列。
public static int startlie(int k,int index[]){
//体现了回溯的想法，若是这时传来的第k行的皇后的列数为-1
//表明该皇后不存在，则从头开始判断；
//若是第k行的皇后有列数，说明以前传入的不正确，
//因此从该列数向后一列进行寻找。
int lie;
if(index[k]==-1)
{
lie=0;
}
else
lie=index[k]+1;
for(int j=lie;j<8;j++)
{
if(isvaild(k,j,index))
{
return j;
}
}
return -1;
}
最后说下主函数：主函数首先须要将以前表明皇后位置的index数组赋初值-1，并初始化第一个数为0，咱们默认将第一个皇后放在左上角。以后要设置一个表明当前寻找的皇后的变量k。以后使用while函数，持续判断k是否小于等于7，初始化变量j表明列数，将第一个判断函数的值赋给j，判断j是否为正数，若是为正数，将j的值赋值index【k】(当前寻找的皇后的位置)，k增一，若是为负数说明，遍历了全部列都没有找到合适的列数，表明以前的皇后位置有误，将index【k】==-1，k减1。
public static void main(String[]args) {
//摆放每行的皇后放在哪列
//index[0]=0，表明第一个皇后放在第0列。
int []index= new int[8];
//初始化每一个皇后是否存在，若是列数为-1，表明不存在
for(int i=0;i<8;i++)
{
index[i]=-1;
}
//第一个设置在第一列
index[0]=0;
//k为如今寻找的皇后
int k=1;
//找完8个皇后
while(k<=7){
int j;
j=startlie(k,index);
//理论大于0就能够，由于第一个皇后位置为0列，因此其余皇后不能再0列
if(j>=0){
index[k]=j;
k++;
}
else
{
//要将当前不合适的皇后的位置置1，
// 理由：好比当前正在寻找k=5，即第六个皇后，第六个皇后没找到正确位置，回溯第五个皇后
//此时可能以为不用将第六个皇后的位置置为-1；由于正在找第六个皇后，因此第六个皇后的位置仍是初始化的-1，
//但假如回溯第五个皇后也没找到正确位置，而第五个皇后存着的位置为原先位置，
// 此时第五个皇后的位置就要变为-1了，然表明没找到第五个皇后，因此须要将没找到的皇后的位置置为-1.
index[k]=-1;
k--;
//
}
}
for(int i=0;i<8;i++)
{
index[i]=index[i]*2+1;
//System.out.print(index[i]);
}
pp(index);
}
这里初学者会对一个地方有问题也就是else以后为何要把index【k】赋值为-1呢，看着意思是表明将k的皇后变为没有找过的皇后。可是有人会说，那好比我一直都是正确的皇后位置，咱们假设找了四（k=4）次都是对的，当我找第五次（k=5）的时候，我第五次没找到皇后位置，为何还要将其赋值-1，我不是在最初的数组index里赋值为-1了么，并且我也没有改变其数值阿。这是初学者很容易犯的问题，答案是：好比我找第五次（k=5），也就是第六个皇后位置错了，我要回溯第五个皇后，此时index【5】能够不改，由于以前就是-1，但假如我回溯第五个皇后，又没有找到对的列数，说明第五个位置也错了，此时又到了else里，若是我只k--，的确这里是回溯到第四个皇后了，可是我第五个皇后的位置没有改仍是以前错误的位置，这样当我寻找完第四个皇后时，去寻找第五个皇后，第五个皇后仍是从错误的位置开始找，就又会找不到，又回去从新找第四个皇后，就陷入了死循环。因此咱们要赋值为-1。
最后的输出函数能够忽略，也能够看看，由于题中给出要求要按照题意输出，这个比较简单就不仔细说了。
原文地址：
网友评论