N-queens problem: Difference between revisions
m
→Python: Niklaus Wirth algorithm: Example program shortened again
m (→{{header|Python}}: Whitespace removed) |
m (→Python: Niklaus Wirth algorithm: Example program shortened again) |
||
Line 12,842:
print(solution)</syntaxhighlight>
The algorithm can be easily improved by using permutations and O(1) sets instead of O(n) lists and by avoiding unnecessary copy operations during recursion. An additional list ''x'' was added to record the solution. On a regular 8x8 board only 5,508 possible queen positions are examined.
<syntaxhighlight lang="python">def queens(
▲ if a: # set a is not empty
▲ for j in a:
▲ if i + j not in b and i - j not in c:
▲ b.add(i + j); c.add(i - j); x.append(j)
▲ yield from queen(i + 1, a - {j})
▲ b.remove(i + j); c.remove(i - j); x.pop()
▲ else:
▲ yield x
for solution in
print(solution)</syntaxhighlight>
| |||