-1

I am learning recursion coding, and I tried a test for myself- the 8-queen puzzle. I check if there is conflict at each step, and backtrack if there is a conflict. But it seems that my code stops backtracking prematurely.

First, I have:

0000
0000
0000
0000

then it changes to:

1000
0000
0000
0000

and then it changes to:

1100
0000
0000
0000

Now the conflict function returns True, and the function stops. Why isn't it calling solve_queen(grid) with:

1010
0000
0000
0000

I think there is something wrong with the two for loops in solve_queen(grid) but I can't get exactly where it went wrong.

My code follows.

import copy

q4_zero = [[0,0,0,0],
           [0,0,0,0],
           [0,0,0,0],
           [0,0,0,0]]


def format_failed(grid):
    if len(grid) != len(grid[0]):
        return True
    elif len(grid) < 4:
        return True
    return False

def row_conflict(grid):
    for row in grid:
        if row.count(1) > 1:
            return True
    return False 

def col_conflict(grid):
    new_grid = [[r[col] for r in grid] for col in range(len(grid[0]))]
    return row_conflict(grid)

def oblique_conflict(grid):
    i_lst = []
    j_lst = []
    row_count = len(grid)
    for i in xrange(row_count):
        if grid[i].count(1) > 0:
            j = grid[i].index(1)
            i_lst.append(i)
            j_lst.append(j)

    for k in xrange(len(i_lst)):
        for m in xrange(len(i_lst) - 1):
            if abs(i_lst[m] - i_lst[m + 1]) == abs(j_lst[m] - j_lst[m + 1]):
                return True

    return False


def conflict(grid):
    if format_failed(grid):
        return True
    elif row_conflict(grid):
        return True
    elif col_conflict(grid):
        return True
    elif oblique_conflict(grid):
        return True
    return False


def solve_queen(__grid):

    res = conflict(__grid)

    if res is True:
        return res

    grid = copy.deepcopy(__grid)
    N = len(grid)

    for i in xrange(N):
        for j in xrange(N):
            if grid[i][j] == 0:
                grid[i][j] = 1
                final_answer = solve_queen(grid)
                if final_answer is not True:
                    return final_answer

                return True

    return grid

print solve_queen(q4_zero)
4

3 回答 3

1

您永远不会将网格单元设置回零。那么回溯应该如何工作呢？

此外，您有一个嵌套循环solve_queen()，但solve_queen()应该是一个递归函数。使用循环或使用递归。

此外，您在solve_queen(). 除了conflict()，您还需要一个is_solved()告诉您何时停止的函数：

if not is_solved(grid):
    return solve_queen(grid)
else return grid

在旁注中，皇后问题更有效地表示为整数数组，其中索引表示行，值表示列。例如，grid[3] 将告诉您第 4 行中皇后的相关列。

使用这种表示，检查冲突要容易得多。此外，您节省了空间，如果您从 4 个皇后增加到 100 亿个，这可能会派上用场。;-)

最后，您绝对应该阅读有关递归和回溯的内容。我怀疑你是否真的理解这些概念中的任何一个。

于 2012-07-17T10:49:40.660 回答
1 
for i in xrange(N):
        for j in xrange(N):
            if grid[i][j] == 0:
                grid[i][j] = 1
                final_answer = solve_queen(grid)
                if final_answer is not True:
                    return final_answer

                return True

假设在以下情况下solve_queen(grid)返回True（确实如此）grid：

1100
0000
0000
0000

所以，你设置final_answer = True.
既然final_answer is not True不满足，就跳过这一行，直接下一行：

return True

因此，由于这条线，您的回溯解决方案实际上是在第一次失败后停止递归。

该怎么办？
提示：您应该预先定义一个基本子句 - 递归何时成立（提示：在您放置 n 个皇后后 - 并在这种情况下返回答案。
如果您发现解决方案错误 - 不要破坏它，只需继续迭代。True如果您仅用尽了所有可能性，则应返回a （因此该return True语句应超出for循环范围）。

于 2012-07-17T10:47:50.457 回答
0

我不知道这是否会有所帮助，但是...您是否尝试过使用不同的数据表示？

8-queen 问题不需要整个 8x8 网格。由于每个皇后将排在不同的行中，因此您只需要一个带有皇后列的 8 数组。

我不了解 Python，所以在这一点上我无法为您提供帮助，但是更改数据格式可能会解决您的问题。

于 2012-07-17T10:14:15.843 回答