N-queens problem: Difference between revisions
Content added Content deleted
m (→Python: Niklaus Wirth algorithm: Code made compact) |
m (→{{header|Python}}: Whitespace removed) |
||
Line 12,843:
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(n: int):
def queen(i: int, a: set):
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)
yield from queen(i + 1, a - {j})
b.remove(i + j)
else:
yield x
b = set()
yield from queen(0, set(range(n)))
| |||