回溯法 n皇后 python 解法二

普通的用二维数组解决python

这儿采用一维数组，即行数做为index，而列数表明array[index]web

输出全部的解数组

global N  # 皇后个数
# global x # 当前解 list类型不须要声明为全局变量！
global SUM  # 当前已找到的可行方案数
N = 4
# x = [0 for i in range(N)]
SUM = 0

def print_solution(x):
    for i in range(len(x)):
        print(x[i], end="")
    print()


def is_safe(k):
    for i in range(k):
        if x[i] == x[k]:
            return False
        if (x[i] - x[k]) == (i - k):
            return False
        if (x[i] - x[k]) == (k - i):
            return False
    return True


def backtrack(t):
    if t >= N:
        global SUM  # 若但愿在局部函数中修改全局变量，则须要先声明，不然会把SUM做为局部变量处理
        SUM += 1
        print_solution(x)
    else:
        for i in range(N):
            x[t] = i
            if is_safe(t):
                backtrack(t + 1)


if __name__ == "__main__":
    x = [0 for i in range(N)]
    backtrack(0)
    print("sum =" + str(SUM))

若只想输出指定个数的解就退出:svg

global N  # 皇后个数
# global x # 当前解 list类型不须要声明为全局变量！
global SUM  # 当前已找到的可行方案数
N = 4
# x = [0 for i in range(N)]
SUM = 0

def print_solution(x):
    for i in range(len(x)):
        print(x[i], end="")
    print()


def is_safe(k):
    for i in range(k):
        if x[i] == x[k]:
            return False
        if (x[i] - x[k]) == (i - k):
            return False
        if (x[i] - x[k]) == (k - i):
            return False
    return True


def backtrack(t):
    # 但其实这样写不怎么好，由于破坏了回溯法的结构
    # 更好的写法是，把判断放到剪纸函数中，这儿即is_safe()中去判断
    global SUM
    if SUM >= 1:  # 达到指望的借个数就退出
        return
    if t >= N:
        # global SUM # 若但愿在局部函数中修改全局变量，则须要先声明，不然会把SUM做为局部变量处理
        SUM += 1
        print_solution(x)
    else:
        for i in range(N):
            x[t] = i
            if is_safe(t):
                backtrack(t + 1)


if __name__ == "__main__":
    x = [0 for i in range(N)]
    backtrack(0)
    print("sum =" + str(SUM))