经典算法之八皇后问题

作者: veaxen 分类: 数据结构与算法,编程题目 发布时间: 2017-04-13 12:03

问题描述:
八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。

下面利用回溯法(递归写法),来求出所有可能的结果:

#include <conio.h>
#include <iostream>
#include <cmath>
#include <stdlib.h>
using namespace std;

#define MAX    8

class QueenPuzzle
{
    int queens[MAX];    //储存每一行皇后的位置,例如qeen[m] = n 表示第m行皇后的位置在n列上
public:
    int sum;    //记录有多少种解法

    QueenPuzzle():sum(0){}

    bool isValid(int m);//判断第m行的皇后是否合法
    void printOut();//打印解法
    void placeQeen(int m);//放置第m个皇后(m刚好就是行号)
};

bool QueenPuzzle::isValid(int m)
{
    for(int i=0;i<m;i++){
        if(queens[i] == queens[m])  //存在在同一列的皇后
            return false;
        if((m-i) == abs(queens[m]-queens[i]))   //在同一个对角线
            return false;
    }
    return true;
}

void QueenPuzzle::printOut()
{
    for(int i=0;i<MAX;i++){
        for(int j=0;j<MAX;j++){
            if(j == queens[i])
                cout<<"1    ";
            else
                cout<<"0    ";
        }
        cout<<endl;
    }

    cout<<endl<<"按q键退出,按其他键继续"<<endl<<endl;

    if(getch() == 'q')
        exit(0);
}

void QueenPuzzle::placeQeen(int m)
{
    if(m == MAX){   //放置了8个皇后了(计数是从0开始的),也就是说发现了一种解法
        sum++;
        cout<<"第"<<sum<<"种解法:"<<endl;
        printOut();
        return;
    }
    for(int i=0;i<MAX;i++){
        queens[m] = i;//放置皇后
        if(isValid(m))
            placeQeen(m+1);//继续放置下一个皇后
    }
}

int main()
{
    QueenPuzzle queen;
    queen.placeQeen(0);
    cout<<"共"<<queen.sum<<"种解法"<<endl;
    return 0;
}

重点是要理解这个回溯法的思想

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.