题目链接:http://lx.lanqiao.cn/problem.page?gpid=T68
时间限制: 1Sec 内存限制: 128MB

题目描述

给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。

输入

输入的第一行为一个整数n，表示棋盘的大小。 
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。 

输出

输出一个整数，表示总共有多少种放法。 

样例输入

4 
1 1 1 1 
1 1 1 1 
1 1 1 1 
1 1 1 1 

样例输出

2

解题思路

八皇后问题，这个只不过在八皇后的基础上，再搜一遍。先放黑皇后，从第一行开始放，如果可以放，那放过之后就放下一行，否则回溯，判断下一列。黑皇后放到最后一行，再放白皇后，直到白皇后也放到头，方案数加一。

#include <bits/stdc++.h>
using namespace std;
int mp[10][10], n, ans = 0;
bool Judge(int r, int c, int s) {//判断是否可以放
    for (int i = r - 1; i >= 0; i--)//向上判断
        if (mp[i][c] == s)
            return false;
    for (int i = r - 1, j = c - 1; i >= 0 && j >= 0; i--, j--)//向左上方向判断
        if (mp[i][j] == s)
            return false;
    for (int i = r - 1, j = c + 1; i >= 0 && j < n; i--, j++)//向右上方向判断
        if (mp[i][j] == s)
            return false;
    return true;
}
void DFS(int r, int s) {
    if (r == n) {//搜到头了
        if (s != 2)//证明白皇后也放好了
            ans++;//方案数加一
        else DFS(0, 3);//黑皇后放好了开始放白皇后
        return;
    }
    for (int i = 0; i < n; i++) {
        if (mp[r][i] == 1) {//证明可以放
            if (Judge(r, i, s)) {//判断
                mp[r][i] = s;//放下该棋子
                DFS(r + 1, s);//进入下一行
                mp[r][i] = 1;//回溯
            }
        }
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &mp[i][j]);
    DFS(0, 2);//先放黑皇后。2代表黑皇后，3代表白皇后
    printf("%d\n", ans);
    return 0;
}