任意皇后数问题（cpp）

任意皇后数问题（cpp）

目录

一、了解八皇后问题产生背景(八皇后问题_百度百科)

二、大体构思

三、分析关键细节

 四、贴码

---

一、了解八皇后问题产生背景(八皇后问题_百度百科)

简言之：

在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，

即任意两个皇后都不能处于同一行、同一列或同一斜线上，问一共有多少种摆法。

二、大体构思

穷举肯定头大，看要求能想到一个8*8的棋盘上，每行必须有且只有1只皇后，现在就是如何给这8行（每行只在某个位置具有皇后）排序的问题了。由此又能展开两种比较intelligible的思路：

1.线性代数：用消元矩阵左乘单位矩阵，然后就线代的方式（矩阵块儿的对角线上不能有两个相同的标识皇后的数字）

2.递归（本例所用）：每行确定了皇后位置后继续按本行的寻找方式确定下一行的皇后位置

先来个小的，使用4*4矩阵，可放置点设为0，不可放置点设为非0(简化代码用)，再好好想象一下“树”分支的创建顺序和销毁顺序（就是一种探索路线结束的顺序），每到一个点就把该点直下，45度左下和右下方向加限制标识，待数据传给下一分支后再恢复原样

三、分析关键细节

       首先能想象出按照时间推进，搜索过程形成的是一个类似二叉树的节点分叉再分叉...的结构，所以出自同一节点（即棋盘上的一个确定的皇后位置）的不同分支间不能相互影响，由此要注意在递归时的了逻辑顺序(递归函数中的数组无论是指针还是普通形式实际上都一直指向同一块内存)，防止不同分支间有数据交互。亦不建议用堆内存复制的方式来解决这个问题（这棵树结构很大，不做好内存释放，调不了几次内存就紧张了(应该是这样)）

        再一个，同一行多个可用点间的切换既要注意消除前一个点造成的影响，又要防止在还原的过程中破坏前几行给后行的点留下的约束

        还有，出现了某一行全部被限制（一个可放置的位置都没有）的时候，说明满行上边一行中对应的起始节点位置下面的所有分支都无解，所以直接换到该起始节点的下一个可用节点继续探索

 四、贴码

#include 
#define NQueens 8 //任意只皇后
//计算最后一行可用的节点数，即为一条7个节点路线末端引出的可用节点数
short count_lastRow(short *s)
{
    short fd = 0;
    for (short d = 0; d < NQueens; d++)
        fd += *(s + d) ? 0 : 1;
    return fd;
}
#include 
using namespace std;
//设置对角线上元素的限制与取消限制
void setDian1(short *ss, short row, short column, short dir, short ax) //0代表左边，非零代表右边
{                                                                      
//注意row和column起点都是1
    if (row < NQueens + 1 && column > 0 && column < NQueens + 1)
    {
        *(ss + (row - 1) * NQueens + column - 1) += ax ? 1 : -1;
        setDian1(ss, row + 1, column + (dir ? 1 : -1), dir, ax);
    }
}
//显示数阵
void print(short ss[][NQueens])
{
    printf("-------one posibility-------n");
    for (short d = 0; d < NQueens * NQueens; d++)
    {
        if (d && d % NQueens == 0)
            cout << endl;
        cout << *(&ss[0][0] + d) << "  ";
    }
    printf("n---------------------------n");
}
//主体递归函数
void k(short x, short pt[NQueens][NQueens], register short &total)
{
    if (x == NQueens)
    {
        total += count_lastRow(pt[NQueens - 1]);
        print(pt);
        return;
    }
    for (short as = 0; as < NQueens; as++)
    {
        if (pt[x - 1][as] == 0) //只有为0才代表空缺，其余情况都是有>=1重条件限制着的
        {
            for (short w = x - 1; w < NQueens; w++)
                pt[w][as] += 1;
            setDian1(&pt[0][0], x, as + 1, 0, 1);
            setDian1(&pt[0][0], x, as + 1, 1, 1); //最后一个参数是标记写和删，1写0删
            pt[x - 1][as] = 5;
            k(x + 1, pt, total);
//把限制过的数阵传给下一分支后清除掉本轮所加限制
            for (short w = x - 1; w < NQueens; w++)
                pt[w][as] += -1;
            setDian1(&pt[0][0], x, as + 1, 0, 0);
            setDian1(&pt[0][0], x, as + 1, 1, 0);
            pt[x - 1][as] = 0;
        }
    }
}
int main()
{
    register short total = 0;
    short w[NQueens][NQueens];
    for (short d = 0; d < NQueens; d++)
    {
        for (short a = 0; a < NQueens; a++)
            w[d][a] = 0;
    }
    k(1, w, total);
    printf("All posibilities total up to %dn", total);
    return 0;
}

PS：对称棋盘的话需要给结果除个2，十皇后算了有将近30秒上下得出不对称解是724个，供参考