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
    
    

4 comments

Ahmed 11 years, 11 months ago  # | flag

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) 11 years, 11 months ago  # | flag

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

Michael Dorner 11 years, 3 months ago  # | flag

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) 11 years, 3 months ago  # | flag

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)
Python recipes (4591)
Filippo Squillace's recipes (12)

Required Modules

  • (none specified)

Other Information and Tasks