N-queens problem: Difference between revisions

Content added Content deleted
m (→‎{{header|Python}}: Whitespace removed)
m (→‎Python: Niklaus Wirth algorithm: Example program shortened again)
Line 12,842: Line 12,842:
print(solution)</syntaxhighlight>
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.
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):
<syntaxhighlight lang="python">def queens(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 queens(i + 1, a - {j})
⚫
b.remove(i + j); c.remove(i - j); x.pop()
⚫
else:
⚫
yield x


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); x.pop()
⚫
else:
⚫
yield x


b = set(); c = set(); x = []
b = set(); c = set(); x = []
yield from queen(0, set(range(n)))
for solution in queens(0, set(range(8))):


for solution in queens(8):
print(solution)</syntaxhighlight>
print(solution)</syntaxhighlight>


Retrieved from "https://rosettacode.org/wiki/N-queens_problem"