Rosetta Code

N-queens problem: Difference between revisions

← Older editNewer edit →
Content deleted Content added
Majow (talk | contribs)
305 edits
Majow (talk | contribs)
305 edits
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 the implicitunnecessary copy operations during recursion. An additional list must''x'' bewas added to record the solution. To achieve a sorted order, ''a.copy()'' can be replaced with ''sorted(a)''. 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.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 - {j})
a.add(j)
b.remove(i + j)
c.remove(i - j)
Line 12,860 ⟶ 12,858:
yield x
 
a = set(range(n))
b = set()
c = set()
x = []
yield from queen(0, set(range(n)))
 
 
Retrieved from "https://rosettacode.org/wiki/N-queens_problem"