It's a faster pythonic solution for backtracking. It combine a list of choice points with a list of choices according to a function that define when a choice is assignable to a choice point. As you see, it's easy to formulate a 8 queens and 4 colors problems.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 | ```
def backtracking(choice_points, choices, assignable):
"""
Template method
choice_points: is a list of the choice points. Each of them will be assigned to a single choice for
each solution.
choices: is a list of choices.
assignable: is a function that declare if a choice is assignable to a choice point.
It needs three arguments:
def assignable(choice, choice_points, solutions):
In particular, solutions store the assignments of the previous choice points.
It seems like that {cp0:c0, cp1:c1, ...} where cpI is a choice point and cI is a choice.
"""
N = len(choices)
M = len(choice_points)
# solutions is the dict that has for each choice point (key) a choice (value)
solutions = {}
cp=0
c=0
backtrack=False
end=False
while(not end):
#forward
while( not backtrack ):
if( assignable( cp, c, solutions ) ):
solutions[cp] = c
if( cp==M-1):
yield {choice_points[k]:choices[v] for k,v in solutions.iteritems()}
del solutions[cp]
if not c==N-1:
c+=1
else:
backtrack = True
else:
cp+=1
c=0
elif( c!=N-1):
c+=1
else:
backtrack=True
#backward
end=(cp==0)
while( backtrack and not end ):
cp-=1
c=solutions.pop(cp)
if( not c==N-1 ):
c+=1
backtrack=False;
elif( cp==0 ):
end=True
if __name__=='__main__':
############## 4 Colors Problem #############
neighbors = [set(), set(),set(),set(),set()]
neighbors[0].add(1)
neighbors[0].add(2)
neighbors[1].add(2)
neighbors[1].add(3)
neighbors[1].add(0)
neighbors[2].add(0)
neighbors[2].add(1)
neighbors[2].add(4)
neighbors[3].add(1)
neighbors[3].add(4)
neighbors[4].add(2)
neighbors[4].add(3)
nations = ['Italy','Spain','France','Germany','England']
colors = ['Yellow','Red','Blue','Black']
def assignable4Colors(nation, color, solutions):
"""
It's assignable a color to a nation if it's empty the intersection between neighbors of nation
and the nations of the same color in solutions.
"""
sameColor = set([n for n,c in solutions.iteritems() if c==color ])
return neighbors[nation].isdisjoint(sameColor)
for s in backtracking(nations, colors, assignable4Colors):
print s
############## 8 Queens Problem ###############
rows = ['1', '2', '3', '4', '5', '6', '7', '8']
columns = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
def assignable8Queens(row, column, solutions):
for r, c in solutions.iteritems():
if c == column:
return False
elif r-c == row-column:
return False
elif r+c == row+column:
return False
return True
for s in backtracking(rows, columns, assignable8Queens):
print s
``` |

Tags: backtracking, python

Hi, when I execute this programme I have a syntax error message !!

yield {choice_points[k]:choices[v] for k,v in solutions.iteritems()} ^ SyntaxError: invalid syntax

Strange it works for me. What version of python do you have? With py3k you have to substitute iteritems() with items()

Hi, I need your held. How would your code look like, if the question would be: Find a possible seating order for the guests, but regarding to their wishes ("person1 wants to sit next to person2", etc.)? Thank you.

Hi, you should create two lists: people and seats.

After that, in order to define the assignable function you have to create a data representation of the "wishes". Probably the best representation would be a dictionary with both key and value persons. For example {"p1":"p2"} means that person1 wants sit next to person2.

Therefore, before assign a person a seat you need to be sure that all the constraints (wishes) are satisfied.