N-queens problem: Difference between revisions

Line 12,841:

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

print(solution)</syntaxhighlight>

The algorithm can be slightly improved by using sets instead of lists ~~(cf. backtracking on permutations)~~. But this makes the algorithm a bit harder to read, since the list x has to be added to record the solution. On a regular 8x8 board only 5,508 possible queen positions are examined. However, because these examples are intended for educational purposes, they are not optimized for resources or speed. The next program (backtracking on permutations) shows a much faster solution that also uses less space on the stack.

The algorithm can be slightly improved by using sets instead of lists. But this makes the algorithm a bit harder to read, since the list x has to be added to record the solution. On a regular 8x8 board only 5,508 possible queen positions are examined.

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