递归实现为以下代码中backtrack方法
非递归实现为以下代码中f_backtrack方法：
#include <iostream>
using namespace std;
int n;
int *x;
int sum;
bool place(int k)
{
for (int j = 1; j < k; j++)
if (abs(x[k] - x[j]) == abs(k - j) || x[j] == x[k])
return false;
return true;
}
void output()
{
sum++; //sum为所有的可行的解
for (int m = 1; m <= n; m++)
{
cout << "<" << m << "," << x[m] << ">"; //这一行用输出当递归到叶节点的时候，一个可行解
}
cout << endl;
}
void f_backtrack(int i)
{
for (int j = 0; j < n; j++)
{ //初始化解向量
x[j] = 1;
}
while (i >= 1)
{
while (x[i] <= n)
{
if (place(i))
{ //得到可行解
if (i == n)
{
output();
break;
} //得到最终可行解，退出
else
{ //得到部分可行解，搜索下一行
i++;
x[i] = 1;
}
}
else
{ //当前解不可行
x[i]++;
}
}
x[i] = 1;
i--;
x[i]++; //回溯
}
}
void backtrack(int i)
{
if (i > n)
{
output();
}
else
{
for (int j = 1; j <= n; j++)
{
x[i] = j;
if (place(i))
{
backtrack(i + 1);
}
else
{
}
}
}
}
int main()
{
n = 8;
sum = 0;
x = new int[n + 1];
for (int i = 0; i <= n; i++)
x[i] = 0;
backtrack(1);
cout << "方案共有" << sum << endl;
}
