Anonymous user
N-queens problem: Difference between revisions
→Alternative Solution
Line 3,351:
for row in range(n):
solutions = [solution+[i+1]
for i in range(BOARD_SIZE)▼
for solution in solutions
▲ for i in range(BOARD_SIZE)
if not under_attack(i+1, solution)]
return solutions
for answer in solve(BOARD_SIZE): print(list(enumerate(answer, start=1)))</lang>
===Simple Backtracking Solution===
A surprisingly simple change to the above code (changing the list comprehension to a generator expression) produces a backtracking solution:
{{works with|Python|2.6, 3.x}}
<lang python># From: http://wiki.python.org/moin/SimplePrograms, with permission from the author, Steve Howell
BOARD_SIZE = 8
def under_attack(col, queens):
return col in queens or \
any(abs(col - x) == len(queens)-i for i,x in enumerate(queens))
def solve(n):
solutions = [[]]
for row in range(n):
solutions = (solution+[i+1]
for solution in solutions # first for clause is evaluated immediately,
# so "solutions" is correctly captured
for i in range(BOARD_SIZE)
if not under_attack(i+1, solution))
return solutions
answers = solve(BOARD_SIZE)
first_answer = next(answers)
print(list(enumerate(first_answer, start=1)))</lang>
===Solution with Backtracking===
| |||