题目描述

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

输入

输入的第一行为一个整数n，表示棋盘的大小。 n小于等于8

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

输出

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

样例输入

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

样例输出

2

思路

题目要求不能同一行，同一列，上下对角线都不可以同时出现两个相同颜色的皇后

假设黑色是2，白色是3，当棋盘不等于1时不能存放皇后，从黑色开始第一行可以就往下一行走，判断每一列中满足行列对角线的坐标改成2，

然后继续下一行找，如果找不到就回溯上一行向下一列移动，然后继续向下找

n = int(input())
mapL = [list(map(int, input().split())) for _ in range(n)]  # 记录棋盘
count = 0  # 计数器def dfs(row, n, s, mapL):global countif row == n:  # 判断是否是放完了最后一行，注意我的行数是从0开始，0代表第一行if s == 2:  # 2代表黑皇后，3代表白皇后dfs(0, n, 3, mapL)  # 黑皇后放完，开始放白皇后if s == 3:  # 全部放完count += 1returnfor i in range(n):if mapL[row][i] != 1:  # 不为1、说明放了皇后，或者不能皇后continueif check(row, i, s, mapL):mapL[row][i] = s  # 可以放，将格子的数字变为放置对应皇后的数字dfs(row + 1, n, s, mapL)mapL[row][i] = 1  # 回溯def check(row, j, s, mapL):r = row - 1k = j - 1for i in range(row - 1, -1, -1):  # 检查对应列if mapL[i][j] == s:return Falsewhile r >= 0 and k >= 0:  # 检查对应左上角if mapL[r][k] == s:return Falser -= 1k -= 1r = row - 1k = j + 1while r >= 0 and k < n:  # 检查对应右上角if mapL[r][k] == s:return Falser -= 1k += 1return Truedfs(0, n, 2, mapL)
print(count)