八皇后问题

题目

设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第1行，第2行……第8行上布放棋子。在每一行中有8个可选择位置，但在任一时刻，棋盘的合法布局都必须满足3个限制条件，即任何两个棋子不得放在棋盘上的同一行、或者同一列、或者同一斜线上。试编写一个递归算法，求解并输出此问题的所有合法布局。（提示：用用回溯法。在第n行第j列安放一个棋子时,需要记录在行方向、列方向、正斜线方向、反斜线方向的安放状态，若当前布局合法，可向下一行递归求解，否则可移走这个棋子，恢复安放该棋子前的状态，试探本行的第j+1列。）

代码

#include <iostream>
#include <set>

using namespace std;//<-这样写不好，懒得改了

set<int> usedCol;
set<int> usedDiag;
set<int> usedADiag;//分别用于标记已经有棋子的列、对角线、反对角线
int record[8];//用于记录解中每一行所放棋子的位置
int ans = 0;//解的个数

bool queen(int);

int main()
{
    queen(1);//从第一行开始
    cout << ans << endl;
    return 0;
}

bool queen(int i)
{
    bool flag = 0;//返回值，标记本行是否有合法位置
    if(i == 8)
    {
        for(int j = 1; j <= 8; ++j)
            //不合法，直接试探下一列
            if(usedCol.find(j)!=usedCol.end() ||
               usedDiag.find(i-j)!=usedDiag.end() ||
               usedADiag.find(i+j)!=usedADiag.end())
                continue;
            //合法，输出一个解
            else
            {
                flag = 1;
                ans++;
                for(int cnt = 0; cnt < 7; ++cnt)
                    cout << '(' << cnt+1 << ',' << record[cnt] << ')';
                cout << "(8," << j << ')' << endl;
            }
        return flag;
    }

    for(int j = 1; j <= 8; ++j)
        //不合法，直接试探下一列
        if(usedCol.find(j)!=usedCol.end() ||
           usedDiag.find(i-j)!=usedDiag.end() ||
           usedADiag.find(i+j)!=usedADiag.end())
            continue;
        else
        {
            //放置棋子
            usedCol.insert(j); usedDiag.insert(i-j); usedADiag.insert(i+j);
            record[i-1] = j;
            //下一行有合法位置
            if(queen(i+1))
                flag = 1;
            usedCol.erase(j); usedDiag.erase(i-j); usedADiag.erase(i+j);
        }
    return flag;
}