classical backtracking algorithm
Python, 30 lines
Download
Copy to clipboard1 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
Is this for Chess?