N皇后问题（子集树、排列树回溯法）

N皇后问题（子集树、排列树回溯法）

> 这题既可以采用子集树也可用排列树

问题描述

解向量

可行性约束

限界约束

代码一：子集树解决

#include <iostream>
using namespace std;
int x[100];       //皇后的位置(i,x[i]),即x[i]表示皇后在i行的列位置
int n;            //棋盘规格
int sum = 0;
bool Place(int t)   //实现限界约束判断
{for (int i = 1; i <t;i++)if(abs(x[t]-x[i])==abs(i-t)||x[i]==x[t])return false;return true;
}
void Backtrack(int t)
{if(t>n){sum++;for (int i = 1; i <= n;i++)cout << "(" << i << "," << x[i] << ")"<< " ";cout << endl;}else{for (int i = 1; i <= n;i++){x[t] = i;if(Place(t))Backtrack(t + 1);}}
}
int main()
{cout << "请输入棋盘规格或者皇后数量" << endl;cin >> n;for (int i = 0; i <= n;i++)x[i] = 0;Backtrack(1);cout << sum << endl;return 0;
}

代码二：排列树解决

#include <iostream>
using namespace std;
int x[100];        //皇后的位置(i,x[i]),即x[i]表示皇后在i行的列位置
int n;            //棋盘规格
int sum = 0;
bool Place(int t)    //实现限界约束判断
{for (int i = 1; i < t;i++)if(abs(i-t)==abs(x[i]-x[t])||x[i]==x[t])return false;return true;
}void Backtrack(int t)
{if(t>n){sum++;for (int i = 1; i <= n;i++)cout << "(" << i << "," << x[i] << ")"<< " ";cout << endl;}else{for (int i = t; i <= n;i++){swap(x[i], x[t]);if(Place(t))Backtrack(t + 1);swap(x[i], x[t]);}}
}
int main()
{cout << "请输入棋盘规格或者皇后数量" << endl;cin >> n;for (int i = 0; i <= n;i++)x[i] = i;Backtrack(1);cout << sum << endl;return 0;
}