N皇后问题解法二
编者：16计外1班 阿沐 指导老师：李老师
1、算法设计
非递归算法：算法思想和解法一相同，用深度优先搜索，并在不满足的约束条件的情况下及时回溯。
2、代码实现（Java）
package gxr;
import java.util.Scanner;
public class QueenTwo {
static int[] a=new int[20];
static int index=0;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.println("请输入皇后个数：");
int n=sc.nextInt();
backdata(n);
System.out.println("“"+n+"皇后问题”的解有 "+index/n+" 个");
}
static void backdata(int n) {
int k;
a[1]=0;
k=1;
while(k>0)
{
a[k]=a[k]+1;
while((a[k]<=n) && (check(k)==0))//为第k个皇后搜索位置
{
a[k]=a[k]+1;
}
if(a[k]<=n)
{
if(k==n)//到这里就表示已经找到了一组满足约束的解
output(n);//输出这组解
else
{
k=k+1;//前k个皇后找到位置，继续为第k+1个皇后找到位置
a[k]=0;//下一个皇后从头开始搜索
}
}
else
{
k=k-1;//回溯过程
}
}
}
private static int check(int k) //该函数是用来判断是否满足约束条件
{
int i;
for(i=1;i<=k-1;i++)//第n个皇后与前面n－1个皇后比较
//判断是否为同一列或者同一对角线
{
if((Math.abs(a[i]-a[k])==Math.abs(i-k)) || (a[i]==a[k]))
{
return 0;
}
}
return 1;
}
private static void output(int n) {
int i;
for(i=1;i<=n;i++)
{
System.out.print(a[i]+" ");
index++;
if(index%n==0)
System.out.println();
}
}
}
3、推演过程
1.初始图如下：（n=4）
a[1]=0;
2.第一步：
a[1]=1;
如图示：
3.第二步：
a[1]=1;
a[2]=1;
如图示：
4.第三步：
a[1]=1;
a[2]=2;
如图示：
5.第四步：
a[1]=1;
a[2]=3;
如图示：
6.第五步：
a[1]=1;
a[2]=3;
a[3]=1;
如图示：
7.第六步：
a[1]=1;
a[2]=3;
a[3]=4;
如图示：
8.第七步：
a[1]=1;
a[2]=4;
如图示：
9.第八步：
a[1]=1;
a[2]=4;
a[3]=1
......
继续循环搜索判断是否符合条件，一旦后继皇后位置出现都不可取时立马回溯，前继皇后位置后移，继续操作......
10.第N步：
找到第一组符合约束条件的解：
a[1]=2;
a[2]=4;
a[3]=1;
a[4]=3;
4、结果显示
5、参考文献：
算法设计与分析吕国英版（第三版） p209（8皇后问题）
6、附件
编者：阿沐
特别声明：该作品为博主原创，若发现哪里写的不对或者对哪部分不明白的请及时联系阿沐
阿沐QQ543206554
Loading...
微信扫一扫，打赏阿沐吧～
评论