首页 > 代码库 > 八皇后

八皇后

问题描述:八皇后问题是把八个皇后放到8*8的棋盘中,使它们不会相互攻击。根据国际象棋规定,皇后可以吃掉和它同行、同列或同一斜线上的任意一个棋子。现要求求出所有可能的解。


解决思路:

       首先把第一个皇后放到棋盘中,再放第二个皇后,使它不会和第一个皇后冲突,再放第三个皇后,依次类推...

为了得到所有的解,我们必须通过循环遍历所有的可能的方案。

       根据已知条件每一行(列)有且仅有一个皇后,所以我仅需要定义一个一维数组q[n],其中n表示行号和皇后编号,数组元素表示列号(从0开始)。例如q[3] = 5,表示第3个皇后(从0开始)被安排的位置是(3, 5)。这样可以便于我们判断皇后的位置是否冲突,所谓的冲突,即该位置的同一行、同一列或同一斜线上已存在了一个皇后。假设现在安排的皇后q[3]=5要判断是否有冲突,我们仅需要判断与q[0-2]是否有列或斜方向上的冲突(行方向无需判断,因为我们定义的是一维数组,行号等于皇后号,也就是说每一行只会对应唯一的皇后),列方向有冲突的条件是q[n] == q[i],斜方向冲突的条件是| q[n] - q[i] | == | n-i |,这样判断较简洁。


TIP:如果点A(x,  y),点B(x1, y1)满足|x - x1| = |y - y1|,则A,B在同一斜方向上


描述如下:

Queen(n)

     for 同一行上的每个位置

        先尝试将第n个皇后放入该位置

        if 和之前已放入的皇后没有冲突

            if(n == 8) 输出该方案

            else Queen(n+1)

End Queen

C++代码:

/**
 * @file EightQueen.cpp
 * @Synopsis 根据已知条件每一行有且仅有一个皇后,所以这里定义一个数组q[MAX],
 *           下标表示行号和皇后编号,数组元素表示列号(从0开始) 
 * @author weih.cao
 * @version 
 * @date 2014-08-19
 */

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

#define MAX 8    //MAX表示皇后最大个数,仅当max = 1 或 max >= 4 时才有解
int q[MAX];                      
int num = 0;

void print()
{
    for(int i = 0; i < MAX; ++i)
    {
        cout << q[i] << " ";
    }
    cout << endl;
}

/* ****************************************************************************/
/**
 * @Synopsis  isDanger 判断新插入的皇后是否与已存在的皇后冲突
 *
 * @Param n表示最新进来的皇后的编号
 *
 * @Returns  有冲突返回true,否则返回false 
 */
/* ****************************************************************************/
bool isDanger(int n)
{
    for(int i = 0; i < n; ++i)
    {
        if(q[n] == q[i] || abs(q[i] - q[n]) == n - i)
            return true;
    }
    return false;
}


/* ****************************************************************************/
/**
 * @Synopsis  queen 安排第n个皇后的位置
 *
 * @Param n表示第几个皇后
 */
/* ****************************************************************************/
void queen(int n)
{
    for(int i = 0; i < MAX; ++i)    // 遍历一列中的每一个位置
    {
        q[n] = i;                   // 先尝试将第n个皇后放入该位置
        if(!isDanger(n))            // 判断该位置是否有危险,如果有危险就尝试下一个位置,
                                    // 否则就安排下一个皇后或输出结果(每个皇后都安排了位置则输出该方案)
        {
            if(n == MAX -1)
            {
                print();            // 打印方案
                ++num;
            }
            else
            {
                queen(n + 1);      // 安排下一个皇后
            }
        }
    }
}

int main()
{
    queen(0);                       //从第0个位置开始安排皇后
    cout << "total: " << num << endl;
}