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

classical backtracking algorithm

Python, 30 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
#!/usr/bin/env python
def back(path):
    if reject(path): return None 
    if issolution(path):
        print path 
    for brother in makebrothers(path):
        if len(path)<8:
            newpath = back(brother)
            if newpath: return newpath
    return None

def issolution(path):
    return len(path)>7
     
def makebrothers(path):
    path = path +[0]
    while path[len(path)-1]<8:
        yield path
        path[len(path)-1]= path[len(path)-1]+1
       
def reject(path):
    t = False
    for i in range(len(path)):
        for j in range(i+1,len(path)):
            if abs((path[j]-path[i])*1.0/(j-i))==1 or path[j]==path[i]: 
                return True
                
    return t
        
back([])

we'll try to generate a list with queen positions in the rows,

path = [x0,x1,..,x7] means queen on row 0 is on column x0

makebrothers will generate sibling solutions in the candidate tree,

issolution means we have a list with len>8,

reject means elements of the list don't atack each other

1 comment

Sunjay Varma 11 years, 2 months ago  # | flag

Is this for Chess?

Created by mihai miulescu on Thu, 30 Sep 2010 (MIT)
Python recipes (4591)
mihai miulescu's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks