问题标题: 酷町堂：八皇后的知识点

“八皇后问题”的相关介绍，见 this 。百度百科也给出了此问题的多种语言的求解。此处给出一个 C++ 语言的版本，可以求解“n 皇后问题”。求解方法为深度优先（Depth First Search, DFS）算法。

#include <iostream>
#include <cmath>
 
using namespace std;
 
//输出所有皇后的坐标,自己想哈
//检查当前列能否放置皇后
bool check(int *queen, int n) 
{
    for(int i = 0; i != n; ++i) //检查横排和对角线上是否可以放置皇后
    {
        if(queen[i] == queen[n] || abs(queen[i] - queen[n]) == (n - i)) {
            return false;
        }
    }
    return true;
}
 
//回溯尝试摆放皇后的位置，n 为横坐标
void put(int* queen, int n, int max, int& sum) 
{
    for(int i = 0; i != max; ++i) {       
        queen[n] = i; //将皇后摆到当前循环到的位置
        if(check(queen, n)) {           
            if(n == max - 1) {
                show(queen, max, sum); //如果全部摆好，则输出所有皇后的坐标
            } else {
                put(queen, n + 1, max, sum); //否则继续摆放下一个皇后
            }
        }
    }
}
 
int main()
{
    //定义皇后的个数，也是棋盘的边长 
    int max;
    cout << "Queens: ";
    cin >> max;
    cout << "--------------------------------------------------" << endl;
    
    //定义棋盘数组。因为只可能每行、每列都是一个棋子，所以没必要使用二维数组， 
    //使用一维数组的索引和值来等价一个二维数组 
    int *queen = new int [max];
    for(int ix = 0; ix != max; ++ix) queen[ix] = 0;
    //记录满足要求的排列的个数 
    int sum=0;
    
    put(queen, 0, max, sum); //从横坐标为 0 开始依次尝试
    
    delete [] queen;
    
    cout << "--------------------------------------------------" << endl;
    cout << "Arrangements: " << sum << endl;
    
    return 0;
}

yuan

推荐题目[USACO1.5]八皇后 Checker Challenge(算法提示:搜索深度优先搜索,DFS)

//OvO（请自己选择……并非强求……）