八皇后问题

作者: HeartGo | 来源:发表于2017-02-07 22:54 被阅读47次

问题描述:

八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例:在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();
    }
}
}

相关文章

  • 11.数据结构—八皇后问题(回溯法)

    11.1 八皇后问题 八皇后问题是以国际象棋为背景的问题:有八个皇后(可以当成八个棋子),如何在 88 的棋盘中放...

  • 算法(03)回溯

    八皇后问题

  • 八皇后问题(N皇后问题)

    八皇后问题是一个经典的递归回溯问题。 描述 八皇后问题是在一个 8*8 的棋盘上放置皇后,要求其放置后满足同一行,...

  • 八皇后问题

    八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在...

  • 八皇后问题

    问题的类别是回溯(backtrace). 回溯通常用递归实现。回溯中注意边界问题,避免越界。同时,剪枝可以减少ca...

  • 八皇后问题

    课堂上老师讲了广度优先搜索算法后让课下实现下八皇后问题,就突发奇想了很多实现方法,这里只把我的实现方式和实现代码粘...

  • 八皇后问题

    问题 八皇后问题是一个古老而著名的问题,是试探法的典型例题。该问题由19世纪数学家高斯1850年手工解决。原题为在...

  • 八皇后问题

    采用试探回溯策略,通过栈记录查找结果,实现八皇后问题求解。 测试代码

  • 八皇后问题

    如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任两个皇后都不能处于同一条横行、纵行或斜线上。 先从第一列开...

  • 八皇后问题

    问题描述: 在8x8的网格上,放置皇后两个皇后,两个皇后之间不能在同一行,也不能在同一列,也不能在对角线上。 cl...

网友评论

    本文标题:八皇后问题

    本文链接:https://www.haomeiwen.com/subject/enomittx.html