N-queens problem: Difference between revisions
m
→Python: Simple Backtracking Solution (Niklaus Wirth Algorithm): Added web link and cosmetics
m (→Python: Simple Backtracking Solution (Niklaus Wirth Algorithm): Added web link and cosmetics) |
|||
Line 12,829:
===Python: Simple Backtracking Solution (Niklaus Wirth Algorithm)===
The following program is a translation of Niklaus Wirth's solution into the Python programming language, but does without the index arithmetic used in the original and uses simple lists instead, which means that the array ''x'' for recording the solution can be omitted. A generator replaces the procedure (see [https://www.inf.ethz.ch/personal/wirth/
<syntaxhighlight lang="python">def queens(n: int, i: int, a: list, b: list, c: list):
if i < n:
Line 12,842:
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, since these two solutions are intended for educational purposes, they are neither resource-friendly nor optimized for speed. The next program (backtracking on permutations) shows a much faster solution that also uses less space on the stack.
<syntaxhighlight lang="python">def queens(
if a: # set a is not empty
for j in a:
if i + j not in b and i - j not in c:
yield from queens(
else:
yield x
for solution in queens(
print(solution)</syntaxhighlight>
| |||