一、【实验目的】1熟悉回溯法的设计步骤2理解搜索策略与搜索空间3掌握N皇后问题的解决方法。二、【实验内容】以4皇后为例进行程序设计即在4x4的棋盘上放置4个皇后任意2个之间不能互相攻击即在同一行、同一列及主、副对角线的平行线上不能有2个及以上的皇后。应用回溯法设计算法求出所有的放置方法。三、实验源代码C语言代码#include stdio.h #define N 4 int a[N]; int count 0; int isSafe(int row, int col){ for(int i 0; i row; i) { if(a[i] col || a[i] - i col - row || a[i] i col row) {//检查列和主副对角线 return 0; } } return 1; } int solve(int row) { if(row N) { for(int i 0; i N; i){ for(int j 0; j N; j) { printf(%d , a[i] j); } printf(\n); } printf(\n); count; return 1; } for(int col 0; col N; col) { if(isSafe(row, col)){ a[row] col; solve(row 1); a[row] 0; } } return 0; } int main(){ solve(0); printf(共有%d个方法, count); return 0; }C代码#include iostream #include vector using namespace std; const int N 4; vectorint a(N); int ans 0; bool isSafe(int row, int col) { for (int i 0; i row; i) { if (a[i] col || a[i] - i col - row || a[i] i col row) { return false; } } return true; } void solve(int row) { if (row N) { for (int i 0; i N; i) { for (int j 0; j N; j) { cout (a[i] j) ; } cout \n; } cout \n; ans; return; } for (int col 0; col N; col) { if (isSafe(row, col)) { a[row] col; solve(row 1); a[row] 0; } } } int main() { solve(0); cout 共有 ans 个方法\n; return 0; }四、实验结果五、实验分析与总结随便写点
