题目描述

一个如下的 6×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 3 个解。最后一行是解的总个数。

样例

输入 #1

6

输出 #1

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

算法1

典型的回溯问题

#include <iostream>
#include <cstdio>
using namespace std;
int n;
int cnt=0;
int a[1000];
int col[1000];//一旦在此列出现过，则后面的每行都不会再次列出现，用来标记此列已被放过
int zhu[1000];//一旦在此点出现过，则这一点所在的对角线上的所有点都不会再出现，用来标记此对角线已被放过
int ci[1000];
void pr(){
    if(cnt>3) return ;//
    else{
        for (int i = 1; i <= n; ++i) {
            printf("%d ",a[i]);
        }
        printf("\n");
    }
}
void dfs(int i) {
    if(i>n) {
        cnt++;
        pr();
    }
    for (int j = 1; j <= n; ++j) {
        if(col[j] ) continue;
        if(zhu[i + j] ) continue;//同一主对角线的坐标的规律横，纵坐标和相同
        if(ci[i - j + n] ) continue;////同一主对角线的坐标的规律横，纵坐标差相同，防止数组(下标为负)越界，后面加上n
        a[i] = j;
        col[j] = 1;
        zhu[i + j] = 1;
        ci[i - j + n] = 1;
        dfs(i + 1);
        col[j] = 0;//回到上一层，恢复
        zhu[i + j] = 0;
        ci[i - j + n] = 0;
    }
}
int main() {
cin >> n;
dfs(1);
cout<<cnt;
return 0;
}

拓展：
n皇后拓展

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。

Input
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

Sample Input
1
8
5
0
Sample Output
1
92
10

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int cnt;
int col[15];
int zhu[30];
int fu[30];
void dfs(int i){
    if(i>n){
        cnt++;
        return;
    }
    else{
        for(int j=1;j<=n;j++){
            if(col[j]) continue;
            if(zhu[i+j]) continue;
            if(fu[i-j+n])  continue;
            col[j]=1;
            zhu[i+j]=1;
            fu[i-j+n]=1;
            dfs(i+1);
            col[j]=0;
            zhu[i+j]=0;
            fu[i-j+n]=0;
        }
    }
}
int main()
{   int sum[15];
    for(int i=1;i<=10;i++){//从1到10先过一遍，会比一遍输入一遍走dfs快很多，因为如果样例都是10，那就得跑好几遍10，特别浪费时间
        cnt=0;//因为每次用完那三个数组都回溯了，所以不用再清0了，每次赋值时用完都又回溯了清掉了
        n=i;
        dfs(1);
        sum[i]=cnt;
    }
    int k;
    while(scanf("%d",&k)&&k!=0){
    printf("%d\n",sum[k]);
    }
    return 0;
}