Solve, time, and profile programs solving the N queens problem in various languages. Solution relies on built-in integer array types.

nqueens.py 1001B

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748
  1. # Look ma, no modules!
  2. # bottlenecks around 12, when the problem size starts to mushroom
  3. board_size = 11
  4. solutions = []
  5. queens = []
  6. occupied = board_size*[0,]
  7. def explore(depth):
  8. # base case
  9. if(depth==board_size):
  10. # stringify/serialize the solution
  11. solutions.append("%s"%(queens))
  12. return
  13. else:
  14. attacked = 2*board_size*[0,]
  15. for i in range(0,len(queens)):
  16. ix1 = queens[i] + depth - i
  17. attacked[ix1] = 1
  18. ix2 = queens[i] - depth + i
  19. attacked[ix2] = 1
  20. for row in range(0,board_size):
  21. if(occupied[row] or attacked[row]):
  22. continue
  23. # make a choice
  24. queens.append(row)
  25. occupied[row] = 1
  26. # explore the consequences
  27. explore(depth+1)
  28. # unmake the choice
  29. queens.pop()
  30. occupied[row] = 0
  31. explore(0)
  32. print "Found %d solutions"%(len(solutions))
  33. #print solutions