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 13 years, 6 months ago

Is this for Chess?

 Created by mihai miulescu on Thu, 30 Sep 2010 (MIT)

### Tags

• (none)
▶ Show machine tags (5)

### Required Modules

• (none specified)