N-queens problem: Difference between revisions
m
→Python: Backtracking on permutations: Restored the original look
m (→Python: backtracking on permutations: Small speed and readability improvements (Python can handle negative indexes)) |
m (→Python: Backtracking on permutations: Restored the original look) |
||
| (4 intermediate revisions by the same user not shown) | |||
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):▼
▲<syntaxhighlight lang="python">def queens(n):
▲ def queen(i):
if i < n:
for k in range(i, n):
if b[i + j] and c[i - j]:
b[i + j] = c[i - j] = False
▲ a[i], a[k] = l, j
b[i + j] = c[i - j] = True
else:
yield a
Line 12,883 ⟶ 12,881:
b = [True] * (2 * n - 1)
c = [True] * (2 * n - 1)
yield from
sum(1 for p in queens(8)) # count solutions▼
▲sum(1 for p in queens(8))
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, restoring the
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
if i < n:
for k in range(i, n):
a[i], a[k] =
if b[i + j] and c[i - j]:
b[i + j] = c[i - j] = False
yield from
b[i + j] = c[i - j] = True
a[i:(n - 1)], a[n - 1] = a[(i + 1):n], a[i]
else:
yield a
Line 12,913 ⟶ 12,909:
b = [True] * (2 * n - 1)
c = [True] * (2 * n - 1)
yield from
| |||