n皇后

题目描述

有一个N * N的矩阵方格和N个棋子，现在需要将N个棋子按要求放置到矩阵方格中。

要求如下：

1.任意两个棋子不能在同一行

2.任意两个棋子不能在同一列

3.任意两个棋子不能在同一对角线上（下图红色线段都为对角线）

根据以上要求，问N个棋子放置到N * N矩阵方格中有多少种放置方案

例如：4 * 4的矩阵方格，4个棋子，有2种放置方案

## 输入描述

输入一个正整数 N(1<N<11)，表示一个 N*N 的矩阵方格和 N 个棋子数量

输出描述

输出 N 个棋子按要求放置到N * N的矩阵方格中有多少种放置方案

样例输入

4

样例输出

2

代码详解

展开查看

N = int(input())

chess = [['O' for i in range(N)] for j in range(N)]

def checkcol(col):
    for row in range(N):
        if chess[row][col] == 'X':
            return False
    return True

def checkslant(row, col):
    for k in range(1, N):
        d = [(k,k), (-k,-k), (k,-k), (-k,k)]
        for i,j in d:
            if 0<=row+i<N and 0<=col+j<N and chess[row+i][col+j] == 'X':

                return False
    return True

def dfs(row):
    global cnt
    if row == N:
        # for i in chess:
        #     for j in i:
        #         print(j, end=' ')
        #     print()
        # print()
        cnt += 1
        return
    for col in range(N):
        if checkcol(col) and checkslant(row, col):
            chess[row][col] = 'X'
            dfs(row+1)
            chess[row][col] = 'O'
cnt = 0
dfs(0)
print(cnt)

运行结果

展开查看

4
2