5

2024-07-01 08:26| 来源: 网络整理| 查看: 265

5-5 n皇后问题（回溯）一、题目描述

在nxn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。在这里插入图片描述

二、分析法一：

以n=4皇后问题为例第一种︰解空间是4叉树每个皇后在一行上有四个可选位置（显式约束∶任两皇后不同行) 在这里插入图片描述

代码 //5-5 n皇后问题 //解空间树是完全N叉树 #include #include #include using namespace std; int n; int sum=0; int x[100];//x[1...n]表示n皇后问题的解; x[i]表示皇后i放在棋盘的第i行的第x[i]列 bool Place(int t){ for(int i=1;i for(int i=1;i sum++; Print(); } for(int i=1;i //cin>>n; n=8; BackTrack(1); cout if(x[i]==x[t] ||abs(i-t)==abs(x[i]-x[t])) return false; } return true; } void Print(){ for(int i=1;i if(t>n){ sum++; Print(); } for(int i=t;i //cin>>n; n=8; for(int i=1;i

【本文地址】

公司简介

联系我们