N-queens problem: Difference between revisions
Content added Content deleted
m (→Python: Niklaus Wirth algorithm: Revised one sentence) |
m (→Python: Niklaus Wirth algorithm: Revised explanation) |
||
| Line 12,841: | Line 12,841: | ||
for solution in queens(8, 0, [], [], []): |
for solution in queens(8, 0, [], [], []): |
||
print(solution)</syntaxhighlight> |
print(solution)</syntaxhighlight> |
||
The algorithm can be easily improved by using sets instead of lists and by avoiding the |
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. |
||
<syntaxhighlight lang="python">def queens(n: int): |
<syntaxhighlight lang="python">def queens(n: int): |
||