八皇后问题

问题描述:

八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例:在8X8格的国际象棋棋盘上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

问题求解:

采用回溯算法,即从第一行开始,依次探查可以放置皇后的位置,若找到,则放置皇后,开始探查下一行;若该行没有位置可以放置皇后,则回溯至上一行,清除该行放置皇后的信息,从该行原本放置皇后的下一个位置开始探查可以放置皇后的位置。求所有解时,每找到一组解,就清除这一组解最后一个皇后的位置信息,开始探查该行另外一个可以放置皇后的位置,依次回溯求解。

public class ThreeQueen {

/**
 * @param args
 */
private int[] a=new int[8];              //存储弟i行皇后位于第a[i]列
public static void main(String[] args) {
    // TODO Auto-generated method stub
ThreeQueen queen=new ThreeQueen(); 
queen.Search(0); 
} 
public void Search(int m){ 
if(m>=8){ 
System.out.println(“八皇后的一组解为:”); 
printResult(); 
} 
else{ 
for(int i=0;i<8;i++){ 
if(CanPlace(m,i)){

                a[m]=i;
                Search(m+1);
                a[m]=-10;
            }
        }
    }
}
private boolean CanPlace(int k,int j) {
    // TODO Auto-generated method stub
    for(int i=1;i<=k;i++){
        if((a[k-i]==j)||(a[k-i]==j-i)||(a[k-i]==j+i)){   //判断左上,右上,该列有没有其他皇后
            return false;}
    }
    return true;


}
private void printResult() {
    // TODO Auto-generated method stub
    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++){
            if(a[i]==j){
                System.out.print("Q");
            }else {
                System.out.print("0");
            }
        }
        System.out.println();
    }
}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

P1903 【模板】分块/带修改莫队(数颜色)

题目描述 墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1、 Q L R代表询问你从第L支画笔到...

34910
来自专栏华章科技

技巧:Excel用得好,天天没烦恼

分析公司DarkHorse Analytics 从美国劳工统计处获得数据,并制作了这张二十四小时会唿吸的地图,显示曼哈顿的工作与在宅人口。

1154
来自专栏数据小魔方

excel数据排序的常用方式

今天跟大家分享几种常用的数据排序方式! ▼ 在excel中整理数据、作图或者其他数据汇总操作,常会遇到对某一列数据排序的需求。当然用肉眼观察手动排序肯定是不现实...

43211
来自专栏游戏杂谈

as3绘制抛物线

一般做页游的过程中,特效的释放可能是不是固定位置的播放,是需要进行“运动的”(其实就是移动特效这个影响剪辑)。举个例子:步兵射箭,不确定箭发射的方向,事先也不...

1062
来自专栏hightopo

HT for Web可视化QuadTree四叉树碰撞检测

1271
来自专栏章鱼的慢慢技术路

Python中的高级turtle(海龟)作图

4212
来自专栏菩提树下的杨过

Metaball(元球)效果学习

几年前就在网上曾看见过这种效果,但一直不知道叫什么名字 ? 前一阵无意在9ria(天地会)论坛上看到了一篇专门讲这个的文章:AS3 元球(Metaball),不...

27010
来自专栏JarvanMo的IT专栏

浅扒Android动态设置字体大小

Android开发中,TextView类的控件应该说是很常用了。一般来说我们是通过android:textSize="20sp" 来设置字体大小,但是很多时候...

1443
来自专栏林德熙的博客

win10 uwp win2d 使用 Path 绘制界面

在 win2d ,可以使用 DrawGeometry 的方式画出几何。而路径 Path 就是一种 Geometry 。传入的 CanvasGeometry 参数...

1231
来自专栏数据小魔方

一款脑洞大开的表格可视化神器

今天跟大家介绍一款任坤大神写的新包——formattable。 这个包的功能很简单,但是却很具创意性,它颠覆了R语言data.frame数据表的呈现方式,允许在...

4838

扫码关注云+社区

领取腾讯云代金券