N-queens problem: Difference between revisions
m
→Python: Niklaus Wirth algorithm: Added a more optimized version.
m (→{{header|Python}}: Heading and sentence shortened) |
m (→Python: Niklaus Wirth algorithm: Added a more optimized version.) |
||
Line 12,841:
for solution in queens(8, 0, [], [], []):
print(solution)</syntaxhighlight>
The algorithm can be slightly improved by using sets instead of lists
<syntaxhighlight lang="python">def queens(i: int, a: set, b: set, c: set, x: list):
if a: # set a is not empty
Line 12,852:
for solution in queens(0, set(range(8)), set(), set(), []):
print(solution)</syntaxhighlight>
However, because these examples are intended for educational purposes, they are not optimized for resources or speed. The next example shows a more optimized solution that also requires less space on the stack.
<syntaxhighlight lang="python">def queens(n: int):
def queen(i: int):
if a: # set a is not empty
for j in a.copy():
if i + j not in b and i - j not in c:
a.remove(j)
b.add(i + j)
c.add(i - j)
x.append(j)
yield from queen(i + 1)
a.add(j)
b.remove(i + j)
c.remove(i - j)
x.pop()
else:
yield x
a = set(range(n))
b = set()
c = set()
x = []
yield from queen(0)
for solution in queens(8):
print(solution)</syntaxhighlight>
|