在做洛谷上的题前我们看一下这样一道题
题目描述
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 × 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。
给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。
输入
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数b(1≤b≤92)。
输出
输出有n行，每行输出对应一个输入。输出应是一个正整数，是对应于b的皇后串。
样例输入
2
1
92
样例输出
15863724
84136275
题目比较
本题比起洛谷上的题目主要是差在已知棋盘大小和解法总数，按给定要求排序，输出相应第几种解法
问题解决
用一个数组模拟棋盘，然后用递归回溯的办法找出相应解法并存在一个数组中，并能复原，最后根据输入，输出相应解法就行
解决关键点
1.建立数组模拟棋盘，存储解法
2.确立边界，什么时候结束该次递归
if (ithQueen == 8) {
count ++;
return;
}3.设计递归算法
int i, k, r;
for(i = 0; i < 8; i++)
if(board[i][ithQueen] == -1)
{
board[i][ithQueen] = ithQueen;
for(k = count; k < 92; k++) queenPlaces[k][ithQueen] = i + 1;
for(k = 0; k < 8; k++)
for(r = 0; r < 8; r++)
if(board[k][r]==-1&&(k==i||r==ithQueen||abs(k-i)==abs(r-ithQueen)))
board[k][r] = ithQueen;
putQueen(ithQueen + 1);4.回溯复原
for(k = 0; k < 8; k++)
for(r = 0; r < 8; r++)
if(board[k][r] == ithQueen) board[k][r] = -1;
完整代码
#include <stdio.h>
#include <math.h>
int queenPlaces[92][8]; //存放 92 种皇后棋子的摆放方法
int count = 0; int board[8][8]; //仿真棋盘
void putQueen(int ithQueen); //递归函数，每次摆好一个棋子
void main()
{ int n, i, j;
for(i = 0; i < 8; i++)
{ for(j = 0; j < 8; j++) board[i][j] = -1;
for(j = 0; j < 92; j++) queenPlaces[j][i] = 0; }
putQueen(0); //从第0 个棋子开始摆放，运行结果是将queenPlaces 生成好
scanf("%d", &n);
for(i = 0; i < n; i++)
{ int ith; scanf("%d", &ith);
for(j = 0; j < 8; j++) printf("%d", queenPlaces[ith - 1][j]);
printf("\n"); }
}
void putQueen(int ithQueen)
{ int i, k, r;
if (ithQueen == 8){ count ++; return; }
for(i = 0; i < 8; i++)
if(board[i][ithQueen] == -1)
{ board[i][ithQueen] = ithQueen;
for(k = count; k < 92; k++) queenPlaces[k][ithQueen] = i + 1;
for(k = 0; k < 8; k++)
for(r = 0; r < 8; r++)
if(board[k][r]==-1&&(k==i||r==ithQueen||abs(k-i)==abs(r-ithQueen)))
board[k][r] = ithQueen;
putQueen(ithQueen + 1);
for(k = 0; k < 8; k++)
for(r = 0; r < 8; r++)
if(board[k][r] == ithQueen) board[k][r] = -1; }
} 基于本题再来看看洛谷p1219这道题
P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
洛谷p1219
解决要点
1.少了棋盘模拟，数据存储，不过这里只需输出前三个解
2.不同的是要计数，棋盘大小会有变化，总解法数也是要输出的
3.设计核心算法递归或dfs
递归设计
1.找出边界
2.每完成一次，要相依回溯处理复原
3.适当使用break,省时
直接看下面代码，有关键注释
完整代码
#include<stdio.h>
int n;
int sum=0;
static int index[15];
static int arr[15][15];
void dfs(int dep,int i) {
for(int j=0; j<n; j++) {
int flag=0;
int k=0;
//竖线上能不能放
while(k<n) {
if(k!=i)
if(arr[k][j]==1) {
flag=1;
break;
}
k++;
}
if(flag==1)
continue;
int m=i;
int l=j;
//斜线（右下）
while(m<n&&l<n) {
m++;
l++;
if(arr[m][l]==1) {
flag=1;
break;
}
}
if(flag==1)
continue;
m=i;
l=j;
//左上
while(m>0&&l>0) {
m--;
l--;
if(arr[m][l]==1) {
flag=1;
break;
}
}
if(flag==1)
continue;
m=i;
l=j;
//...
while(m>0&&l<n) {
m--;
l++;
if(arr[m][l]==1) {
flag=1;
break;
}
}
if(flag==1)
continue;
m=i;
l=j;
//...
while(m<n&&l>0) {
m++;
l--;
if(arr[m][l]==1) {
flag=1;
break;
}
}
if(flag==1)
continue;
arr[i][j]=1;
index[dep]=j+1;
if(dep==n-1) {
if(sum<=2) {
for(int q=0; q<n-1; q++)
printf("%d ",index[q]);
printf("%d\n",index[n-1]);
}
sum++;
}
i++;
dep++;
//递归
dfs(dep,i);
//回溯复原
dep--;
i--;
arr[i][j]=0;
}
}
int main() {
scanf("%d",&n);
dfs(0,0);
printf("%d",sum);
return 0;
}