arrangements backtracking python

Question

I have a hard time trying to figure out how to generate the arrangements via backtracking on python, it is something they asked us at university

A group of n (n<=10) persons, numbered from 1 to n are placed on a row of chairs, but between every two neighbor persons some conflict of interests appeared. Display all the possible modalities to replace the persons, such that between any two persons in conflict stays one or at most two other persons.

I managed to modify the code for the permutations and the queens but i don`t really know where to put the condition for example k is the number and k must be different from the previous number in the string +1 and must bee different from the next number+1

The list of person sitting on the chairs is 1 2 3 4 (is impossible for less then 3 persons) one right solution will be 1 3 4 2 and 3 1 4 2

Here is the code:

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

Code:

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

Test code:

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])

Results:

------------------------------
------------------------------
[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]

Answer 2

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)))