N-queens problem: Difference between revisions
m
→{{header|Python}}: Heading and sentence shortened
m (→Python: Simple Backtracking Solution (Niklaus Wirth Algorithm): Added web link and cosmetics) |
m (→{{header|Python}}: Heading and sentence shortened) |
||
Line 12,828:
print(list(enumerate(first_answer, start=1)))</syntaxhighlight>
===Python:
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/ Niklaus Wirth] or [https://informatika-21.ru/ADen/ Fyodor Tkachov]: Algorithms and Data Structures, pages 114 to 118). On a regular 8x8 board only 15,720 possible queen positions are examined.
<syntaxhighlight lang="python">def queens(n: int, i: int, a: list, b: list, c: list):
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,
<syntaxhighlight lang="python">def queens(i: int, a: set, b: set, c: set, x: list):
if a: # set a is not empty
| |||