python - Can we solve N Queens without backtracking? and How to calculate and what will be the complexity of the backtracking solution? -

i have tried solving problem backtracking , prints possible solutions.

two questions came up:

1.can implement n queen using other techniques?

2.is possible make code below print first solution , terminate?

my current code uses backtracking:

n = 8  x = [-1 x in range(n)]  def safe(k,i):     j in xrange(k):           if x[j] ==  or abs(x[j] - i) == abs(k - j) :           return false     return true   def nqueen(k):     in xrange(n):         if safe(k,i):             x[k] =          if k == n-1:             print "solution", x         else:             nqueen(k+1)  nqueen(0) 

note: interested in techniques not depend on particular programming language.

according wikipedia, can using heuristics:

this heuristic solves n queens n ≥ 4. forms list of numbers vertical positions (rows) of queens horizontal position (column) increasing. n 8 eight queens puzzle.

1. if remainder dividing n 6 not 2 or 3 list numbers followed odd numbers ≤ n
2. otherwise, write separate lists of , odd numbers (i.e. 2,4,6,8 - 1,3,5,7)
3. if remainder 2, swap 1 , 3 in odd list , move 5 end (i.e. 3,1,7,5)
4. if remainder 3, move 2 end of list , 1,3 end of odd list (i.e. 4,6,8,2 - 5,7,9,1,3)
5. append odd list list , place queens in rows given these numbers, left right (i.e. a2, b4, c6, d8, e3, f1, g7, h5)

this heuristics o(n) since it's printing result after if statements.

regarding second question: "is possible make code below print first solution , terminate?"

you can call sys.exit(0) after print:

 import sys n = 8  x = [-1 x in range(n)]  def safe(k,i):     j in xrange(k):           if x[j] ==  or abs(x[j] - i) == abs(k - j) :           return false     return true   def nqueen(k):     in xrange(n):         if safe(k,i):             x[k] =              if k == n-1:                 print "solution", x                 sys.exit(0)             else:                 nqueen(k+1)  nqueen(0) 

or, alternatively can return value , propagate value if indicates termination:

 n = 8  x = [-1 x in range(n)]  def safe(k,i):     j in xrange(k):           if x[j] ==  or abs(x[j] - i) == abs(k - j) :           return false     return true   def nqueen(k):     in xrange(n):         if safe(k,i):             x[k] =              if k == n-1:                 print "solution", x                 return true # found solution, send news!             else:                 if nqueen(k+1): # news!                     return true # share news parent!     return false # have searched every possible combinations, , regret tell not find solution.  nqueen(0) 

as time complexity, since it's complete search, it's n^n. although due pruning (using safe(k,i), in practice it's lot faster.