题目描述

1. N皇后
   https://leetcode-cn.com/problems/n-queens/

算法1

代码

class Solution(object):
    def solveNQueens(self, n):
        """
        51. N皇后
        is_valid
            1.列冲突
            2.斜冲突
                差相等
                和相等

        传/得到 的是下标数组cols
        cols = [1, 3, 0, 2]
        .Q..  1
        ...Q  3
        Q...  0
        ..Q.  2
        """
        res = []
        self.dfs(n, [], res)
        return [['.' * i + 'Q' + '.' * (n - i - 1) for i in q] for q in res]

    def dfs(self, n, cols, res):
        row = len(cols) # 一开始是 第0行
        if row == n:
            res.append(list(cols))
            return 

        for col in range(n): # 第0列开始
            #判断这个点合不合法（row, col)
            if not self.is_valid(cols, row, col):
                continue
            cols.append(col)
            self.dfs(n, cols, res)
            cols.pop()

    def is_valid(self, cols, row, col):
        for r, c in enumerate(cols):# 遍历已存在位置
            if c == col: #列方向有攻击
                return False
            #斜线有攻击：行列之和相等/行列之差相等
            if r - c == row - col or r + c == row + col:
                return False
        return True

算法2 y总

代码

对角线映射到下标
正： y = x + b        b = y - x + n(偏移量保证正）
反： y = -x + b       b = y + x
用截距表示编号

直接传行数, 在g上直接改
class Solution(object):
    def solveNQueens(self, n):
        """
        51. N皇后
            传行数
        """
        g = [['.' for i in range(n)] for j in range(n)]
        cols = [0] * n
        dg = [0] * (2 * n)
        udg = [0] * (2 * n)
        self.res = []
        self.dfs(0, n, cols, g, dg, udg)
        return self.res

    def dfs(self, row, n, cols, g, dg, udg):
        if row == n:
            res = []
            for i in range(n):
                res.append(''.join(g[i]))
            self.res.append(res)
            return 

        for c in range(n):
            if cols[c] or dg[n + c - row] or udg[c + row]:
                continue

            g[row][c] = 'Q'
            cols[c] = dg[n + c - row] = udg[c + row] = True
            self.dfs(row + 1, n, cols, g, dg, udg)
            cols[c] = dg[n + c - row] = udg[c + row] = False
            g[row][c] = '.'

题目描述

AcWing 1114. 棋盘问题
https://www.acwing.com/problem/content/description/1116/

求给定棋盘方案总数
关键是 k个棋子, 并不是每一行都得放
所以算法2简单很多, 直接传行数
算法1  如果不放 cols + ['F'] 传下去 会超时
res = 0
def main():
    while True:
        global res
        res = 0
        n, k = map(int, input().split())
        if n == -1:
            break
        board = [[0] * n for i in range(n)]
        cols = [0] * n
        for i in range(n):
            row = list(input())
            for j in range(len(row)):
                board[i][j] = row[j]

        dfs(n, k, 0, 0, board, cols)
        print(res)

def dfs(n , k, row, num, board, cols):
    '''
    row: 第几行
    num: 已经放了几个棋子
    '''
    global res
    if num == k:
        res += 1
        return 
    if row == n:
        return 
    # 直接跳过这一行
    dfs(n, k, row + 1, num, board, cols)
    # 这一行放棋子
    for i in range(n):
        if board[row][i] == '.' or cols[i]:
            continue
        cols[i] = True
        dfs(n, k, row + 1, num + 1, board, cols)
        cols[i] = False
main()