利用搜索树来解决N皇后有关问题

利用搜索树来解决N皇后问题

?

数据结构里面有个比较著名的八皇后问题，其解决方式倒有很多种，而搜索树又算是一个人工智能方面的入门的思想和手段了。下面就说下如何用搜索树来解决N皇后问题

以四皇后问题为例,如图：

?

?

在第零层，只有一个根节点

在第一层，有四个节点符合符合条件，故根节点有四个子节点

在第二层，各个子节点又具有不同的节点，所以，这棵树继续往下生长，直至长到第4层，也就是说找到了解，那么第四层的节点就是这个四皇后问题的解了。（注意，这里可以采用深度优先搜索与广度优先搜索，各有利弊）

同样的理论和方法，利用这个搜索树可以实现寻找出所有形式的皇后问题的解，下面就附上C++的源代码

?

#include <list>#include <iostream>const int SIZE = 8; //这个是皇后问题的个数const char Queue = '*'; //表示该点已经存在皇后了const char Valid = ' '; //表示该点还可以放置皇后const char Invalid = '_'; //表示该点因不符合条件而不能放置皇后//定义搜索树的节点，这个节点包含节点的高度及盘面状态（利用数组来保存）typedef struct _QueueNode{    char map[SIZE][SIZE];    int height;} QueueNode;//根据给定的位置来更新相应节点中的盘面信息void updateMapByPosition(QueueNode *node, int position){    //此更新横行    for (int i = 0; i != SIZE; i++)    {        if (i != position)        {            node->map[node->height][i] = Invalid;        }    }    //更新竖行    for (int i = 0; i != SIZE; i++)    {        if (i != node->height)        {            node->map[i][position] = Invalid;        }    }    //更新斜行    for (int i = 0; i != SIZE; i++)    {        for (int j = 0; j != SIZE; j++)        {            if (((i + j) == (position + node->height)) && node->map[i][j] == Valid)            {                node->map[i][j] = Invalid;            }            if (((i - j) == (node->height - position)) && node->map[i][j] == Valid)            {                node->map[i][j] = Invalid;            }        }    }}//这个用来搜索子节点并更新queueListvoid collectNextNodes(std::list<QueueNode*> &queueList, QueueNode *node){    QueueNode *tempNode = NULL;    if (node->height >= SIZE)    {        return;    }    for (int i = 0; i != SIZE; i++)    {        if (node->map[node->height][i] == Valid)        {            tempNode = new QueueNode;            for (int j = 0; j != SIZE; j++)            {                for (int k = 0; k != SIZE; k++)                {                    tempNode->map[j][k] = node->map[j][k];                }            }            tempNode->height = node->height;            tempNode->map[tempNode->height][i] = Queue;            updateMapByPosition(tempNode, i);            tempNode->height++;            queueList.push_back(tempNode);        }    }}int main(){    std::list<QueueNode*> queueList; //存储中间盘面的节点    std::list<QueueNode*> solution;  //存储符合皇后问题的节点    queueList.clear();    solution.clear();    QueueNode *node = new QueueNode;    //创建初始的空盘面节点，其高度为1    for (int j = 0; j != SIZE; j++)    {        for (int k = 0; k != SIZE; k++)        {            node->map[j][k] = Valid;        }    }    node->height = 0;    queueList.push_back(node);    while (!queueList.empty())    {        QueueNode *tempNode = queueList.front();        queueList.pop_front();        collectNextNodes(queueList, tempNode);        //如果高度等于SIZE（即得到解）,则入到solution队列中，否则删除掉，释放资源        if (tempNode->height == SIZE)        {            solution.push_back(tempNode);        }        else        {            delete tempNode;        }    }    //这里作为一个数据鉴别，表明一共有多少个符合条件的答案    std::cout << solution.size()<<std::endl;    //这里只是作为一个展示打印出第一个而已，也可以以别的方式处理    node = solution.front();    if(node != NULL)    {        for (int j = 0; j != SIZE; j++)        {            for (int k = 0; k != SIZE; k++)            {                std::cout.put(node->map[j][k]).put(' ');            }            std::cout << std::endl;        }    }}

?

?赋予SIZE不同的数值就可以得出不同的解，这里我只是打印出了第一个解，其余的解都已经存在于solution中，可以自己去处理下

皇后问题的解依照其问题的大小而不同，而随着数据的增大，其空间复杂度几乎就是呈指数形式的增长，在我的电脑上跑下SIZE=15的时候就挂了....

当然皇后问题也不止这一种解决方法，还有诸如贪心算法等可以解决，也可以说是各取所需吧。