N-queens problem: Difference between revisions

Line 12,841:

for solution in queens(8, 0, [], [], []):

print(solution)</syntaxhighlight>

The algorithm can be easily improved by using O(1) sets instead of O(n) lists and by avoiding ~~the implicit~~ copy operations during recursion. An additional list ~~must~~ be 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.

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):

def queen(i: int, a: set):

if a: # set a is not empty

for j in a~~.copy()~~:

for j in a:

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)

yield from queen(i + 1, a - {j})

a.add(j)

b.remove(i + j)

c.remove(i - j)

Line 12,860:

Line 12,858:

yield x

a = set(range(n))

b = set()

c = set()

x = []

yield from queen(0)

yield from queen(0, set(range(n)))