首页 文章

8个女王拼图 - 使用python进行递归

提问于
浏览 次
2

我正在尝试解决8-queens puzzle，也称为n-queens算法 .

我的功能应该计算在NxN板上放置N个皇后的合法方式 .

我几乎得到了它，但不得不做一些丑陋的补丁，使其工作 . 你能帮我解决一下吗？

我做了什么的简介：试图找出在NxN表中设置N个皇后有多少合法方法，我试图在（N-1）xN情况下使用递归来解决（删除第一列）至于事实在同一列上不允许两个皇后，我使用列表长度N.每个单元格代表一列，在每列中我设置皇后设置的行号 .

例如，

[0, 4, 7, 5, 2, 6, 1, 3]

意思是：

  • 第0列 - 皇后放在第0行

  • 第1栏 - 女王排在第4行

  • 第2栏 - 女王排在第7行

  • 第3栏 - 女王排在第5行

  • 第4栏 - 女王放在第2行

  • 第5栏 - 女王排在第6行

  • 第6栏 - 女王放在第1行

  • 第7栏 - 女王放在第3排

困扰我的是我不知道如何省略非法女王的放置 . 所以为了使它工作，我使用一个名为 sum 的全局变量，只有当递归达到合法的完全放置的皇后时才增加它 .

def is_available(n, table, column, N):
    return not any(t in (n, n - i, n + i)
                   for t, i in zip(table, range(column, 0, -1)))

def queens_sum(N):
    table = [0]*N
    global sum
    sum = 0
    solve(N, table, 0, len(table))
    return sum

def solve(N, table, column, end):

    global sum

    if column == end:
        sum += 1
        return None

    for n in range(N):
        # if no other queen can attack here, place a queen in this row 
        if is_available(n, table, column, N):
            table[column] = n
            # Omit the current column at the start
            solve(N, table, column+1, end)
        #else: we can't place queen here, we should abort this direction
            # do nothing

对于 N = 8 我得到 sum = 92 ..因此我知道它有效，但我想避免这个全局反击 .

你能帮我吗？

python n-queens

1 回答

  • 2

    您可以使用solve的返回值来跟踪总和：

    def queens_sum(N):
    return solve(N, [0]*N, 0, N)

def solve(N, table, column, end):
    if column == end:
        return 1

    sum = 0
    for n in range(N):
        # if no other queen can attack here, place a queen in this row 
        if is_available(n, table, column, N):
            table[column] = n
            # Omit the current column at the start
            sum += solve(N, table, column+1, end)
        #else: we can't place queen here, we should abort this direction
            # do nothing

    return sum
    回复于

相关问题