首页 > 代码库 > 八皇后
八皇后
问题描述:八皇后问题是把八个皇后放到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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。