python - 安排回溯python

Question

我很难弄清楚如何通过在 python 上回溯来生成安排，这是他们在大学问我们的问题

一组从 1 到 n 编号的 n (n<=10) 人被放在一排椅子上，但每两个相邻的人之间出现了一些利益冲突。显示替换人员的所有可能方式，以便在冲突中的任何两个人之间保持一个或最多两个其他人。

我设法修改了排列和皇后的代码，但我真的不知道在哪里放置条件，例如 k 是数字，k 必须与字符串 +1 中的前一个数字不同，并且必须不同于下一个数字+1

坐在椅子上的人的名单是 1 2 3 4（少于 3 人是不可能的）一个正确的解决方案是 1 3 4 2 和 3 1 4 2

这是代码：

class Permutations(Backtracking):

    def __init__(self, n):
        Backtracking.__init__(self, n)

    def _init_value(self, k):
        return 0

    def _next_value(self, n, k, v):
        if v < n:
            return v + 1
        return None

    def _cond(self, k, possible, v):
        if v is None:
            return False
        try:
            possible[:k].index(v) 
            return False
        except ValueError:
            return True

    def _solution(self, n, k, possible):
        return k == n-1

    def _handle_solution(self, n, k, possible):
        print(possible)

Answer 1

def chairs(soln, i=0):
    if i == len(soln):
        yield tuple(soln)
    for j in xrange(i, len(soln)):
        if i == 0 or soln[j] not in (soln[i - 1] + 1, soln[i - 1] - 1):
            soln[i], soln[j] = soln[j], soln[i]
            for s in chairs(soln, i + 1):
                yield s
            soln[i], soln[j] = soln[j], soln[i]

print list(chairs(range(1, 5)))

Answer 2

代码：

def possible_solution(remaining, sol=None):
    sol = sol or []
    if not remaining:
        yield sol
    else:
        for i, candidate in enumerate(remaining):
            if not sol or abs(sol[-1] - candidate) != 1:
                new_sol = sol + [candidate]
                new_remaining = remaining[:i] + remaining[i+1:]
                for x in possible_solution(new_remaining, new_sol):
                    yield x

测试代码：

def possible_solutions(neighbors):
    for solution in possible_solution(neighbors):
        print solution

print '-' * 30
possible_solutions([1, 2, 3])

print '-' * 30
possible_solutions([1, 2, 3, 4])

print '-' * 30
possible_solutions([1, 2, 3, 4, 5])

结果：

------------------------------
------------------------------
[2, 4, 1, 3]
[3, 1, 4, 2]
------------------------------
[1, 3, 5, 2, 4]
[1, 4, 2, 5, 3]
[2, 4, 1, 3, 5]
[2, 4, 1, 5, 3]
[2, 5, 3, 1, 4]
[3, 1, 4, 2, 5]
[3, 1, 5, 2, 4]
[3, 5, 1, 4, 2]
[3, 5, 2, 4, 1]
[4, 1, 3, 5, 2]
[4, 2, 5, 1, 3]
[4, 2, 5, 3, 1]
[5, 2, 4, 1, 3]
[5, 3, 1, 4, 2]