八皇后问题

queue.py

N = 8

def isVaild(path, dcolumn):
    drow = len(path)
    for row, column in enumerate(path):
        if column + drow - row == dcolumn:
            return False
        if column - (drow - row) == dcolumn:
            return False
    return True

def backtrace(path, choice):
    if (len(path) == N):
        print(path)
    else:
        for c in list(choice):
            # 去掉isValid这个条件，就变成了一个全排列算法
            if (not isVaild(path, c)):
                continue
            path.append(c)
            choice.remove(c)
            backtrace(path, choice)
            path.remove(c)
            choice.append(c)

def main():
    path = []
    choice = [i for i in range(N)]
    backtrace(path, choice)


if __name__ == "__main__":
    main()