利用搜索树来解决N皇后问题 |
您所在的位置：网站首页 › 王后的画法 › 利用搜索树来解决N皇后问题 |
利用搜索树来解决N皇后问题
|
数据结构里面有个比较著名的八皇后问题，其解决方式倒有很多种，而搜索树又算是一个人工智能方面的入门的思想和手段了。下面就说下如何用搜索树来解决N皇后问题 以四皇后问题为例,如图：
在第一层，有四个节点符合符合条件，故根节点有四个子节点 在第二层，各个子节点又具有不同的节点，所以，这棵树继续往下生长，直至长到第4层，也就是说找到了解，那么第四层的节点就是这个四皇后问题的解了。（注意，这里可以采用深度优先搜索与广度优先搜索，各有利弊） 同样的理论和方法，利用这个搜索树可以实现寻找出所有形式的皇后问题的解，下面就附上C++的源代码 #include #include 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; } } } } //这个用来搜索子节点并更新queueList void collectNextNodes(std::list &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 queueList; //存储中间盘面的节点 std::list 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 |
在第零层，只有一个根节点【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |