N-queens problem: Difference between revisions
m
→Python: backtracking on permutations: Adjusted a few final details
m (→Python: backtracking on permutations: Variable l replaced by h (1 and l look too similar in the source code)) |
m (→Python: backtracking on permutations: Adjusted a few final details) |
||
Line 12,858:
print(solution)</syntaxhighlight>
===Python:
Queens positions on a n x n board are encoded as permutations of [0, 1, ..., n]. The algorithms consists in building a permutation from left to right, by swapping elements of the initial [0, 1, ..., n], recursively calling itself unless the current position is not possible. The test is done by checking only diagonals, since rows/columns have by definition of a permutation, only one queen.
This is initially a translation of the Fortran 77 solution. The solutions are returned as a generator, using the "yield from" functionality of Python 3.3, described in [https://www.python.org/dev/peps/pep-0380/ PEP-380]. On a regular 8x8 board only 5,508 possible queen positions are examined.
<syntaxhighlight lang="python">def queens(n: int):▼
def queen(i: int):▼
▲<syntaxhighlight lang="python">def queens(n):
▲ def queen(i):
if i < n:
for k in range(i, n):
Line 12,889 ⟶ 12,887:
92</syntaxhighlight>
The preceding function does not enumerate solutions in lexicographic order, see [[Permutations#Recursive implementation]] for an explanation. The following does, but is almost 50% slower, because the exchange is always made (otherwise,
However, it may be interesting to look at the first solution in lexicographic order: for growing n, and apart from a +1 offset, it gets closer and closer to the sequence [http://oeis.org/A065188 A065188] at OEIS. The first n for which the first solutions differ is n=26.
<syntaxhighlight lang="python">def queens_lex(n: int):
def queen(i: int):
if i < n:
for k in range(i, n):
| |||