N-queens problem: Difference between revisions
m
→Python: Niklaus Wirth algorithm: The explicit copying of the set a is made implicit again.
m (→Python: Niklaus Wirth algorithm: Revised explanation) |
m (→Python: Niklaus Wirth algorithm: The explicit copying of the set a is made implicit again.) |
||
Line 12,841:
for solution in queens(8, 0, [], [], []):
print(solution)</syntaxhighlight>
The algorithm can be easily improved by using permutations and O(1) sets instead of O(n) lists and by avoiding
<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)
c.add(i - j)
x.append(j)
yield from queen(i + 1, a - {j})
b.remove(i + j)
c.remove(i - j)
Line 12,860 ⟶ 12,858:
yield x
b = set()
c = set()
x = []
yield from queen(0, set(range(n)))
| |||