Welcome, guest | Sign In | My Account | Store | Cart

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.

Python, 108 lines
 ``` 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 ```

Ahmed 9 years, 7 months ago

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

Filippo Squillace (author) 9 years, 7 months ago

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

Michael Dorner 8 years, 12 months ago

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.

Filippo Squillace (author) 8 years, 12 months ago

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.

 Created by Filippo Squillace on Sun, 3 Jul 2011 (MIT)

### Required Modules

• (none specified)