一、问题描述

在n行n列的棋谱上，放n个棋子，保证：这n个棋子任意两个不在同一行，不在同一列，并且也不在对角线上，这样的摆法有多少种？

二、解题思路

使用递归回溯解题。
定义一个一维数组，下标存放列，值存放行。
n表示为n行n列的棋谱，n个棋子
首先从第一列开始放，然后再放第二列，放第二列时需与第一列时比较，是否在同一行或者同一列或者对角线上。如果是，重新摆放第二列的位置；如果不是，继续下一列。摆放第k列时，需与前k-1列相比较是否符合规则，不符合重新摆放第k列的位置，若第k列所有行摆放都不符合规则，则回溯到第k-1列进行与前k-2列进行比较；符合的话进行第k+1列。当将n列全部都放完之后(说明这n列摆放符合规则)，回溯到第n列重新摆放，如果不符合规则继续回溯到第n-1列……依次类推直到所有情况都检测完为止

三、代码实现

#include <iostream>
#include <cmath>

using namespace std;

const int MAXSIZE=20;
int *t=new int[MAXSIZE];//n行n列
int sum=0;//解数

bool place(int i){
    if(i<=1){
        //当为第一列时，前边没有列，无需比较
        return true;
    }
    for(int s=1; s<i; s++)
        //第i列与第s列(一定在第i列之前)在对角线或者在同一行时
        if(abs(t[i]-t[s])==i-s||t[i]==t[s])
            return false;
    return true;
}

void backTrack(int i,int n){
    if(i>n){
        //n行全部试完，解数+1 ，回溯
        cout<<"(";
        for(int k=1;k<=n;k++){
            if(k==n){
                cout<<t[k]<<")"<<endl;
                break;
            }
            cout<<t[k]<<",";
        }
        sum++;
        return;
    }
    for(int j=1; j<=n; j++){
        //第i列 第j行
        t[i]=j;
        if(place(i))
         	//
            backTrack(i+1,n);
    }
}

int main(){
    cout<<"几皇后？"<<endl;
    int n;
    cin>>n;
    backTrack(1,n);
    cout<<sum;
    return 0;
}