N-queens problem: Difference between revisions
m
→Python: Backtracking on permutations: Restored the original look
m (→Python: Niklaus Wirth algorithm: Code made compact) |
m (→Python: Backtracking on permutations: Restored the original look) |
||
(8 intermediate revisions by 2 users not shown) | |||
Line 11,360:
=={{header|Phix}}==
<!--
<syntaxhighlight lang="phix">
with javascript_semantics
--
-- demo\rosetta\n_queens.exw
-- =========================
--
sequence co, -- columns occupied
-- (ro is implicit)
fd, -- forward diagonals
bd,
board
atom count
procedure solve(integer row, integer N, integer show)
for col=1 to N do
if not co[col] then
integer fdi = col+row-1,
bdi = row-col+N
if not fd[fdi]
and not bd[bdi] then
board[row][col] = 'Q'
co[col] = true
fd[fdi] = true
bd[bdi] = true
if row=N then
if show then
puts(1,join(board,"\n")&"\n")
end if
else
end if
board[row][col] = '.'
co[col] = false
fd[fdi] = false
bd[bdi] = false
end if
end if
end for
end procedure
procedure n_queens(integer N=8, integer show=1)
co = repeat(false,N)
fd = repeat(false,N*2-1)
bd = repeat(false,N*2-1)
board = repeat(repeat('.',N),N)
count = 0
solve(1,N,show)
printf(1,"%d queens: %d solutions\n",{N,count})
end procedure
for N=1 to iff(platform()=JS?12:14) do
n_queens(N,N<5)
end for
</syntaxhighlight>
{{out}}
<pre>
Line 12,842 ⟶ 12,843:
print(solution)</syntaxhighlight>
The algorithm can be easily improved by using permutations and O(1) sets instead of O(n) lists and by avoiding unnecessary copy operations during recursion. An additional list ''x'' was added to record the solution. On a regular 8x8 board only 5,508 possible queen positions are examined.
<syntaxhighlight lang="python">def queens(
if a: # set a is not empty
if
else:
yield x
b = set(); c = set(); x = []
for solution in queens(0, set(range(8))):
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 sub(i: int):
for k in range(i, n):
j = a[k]
a[i], a[k] = a[k], a[i]
b[i + j] = c[i - j] = False
yield from sub(i + 1)
a[i], a[k] = a[k], a[i]
else:
yield a
a = list(range(n))
b = [True] * (2 * n - 1)
c = [True] * (2 * n - 1)
yield from sub(0)
sum(1 for p in queens(8)) # count solutions
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):
for k in range(i, n):
j = a[k]
a[i], a[k] = a[k], a[i]
if b[i + j]
yield from sub(i + 1)
a = list(range(n))
b = [True] * (2 * n - 1)
c = [True] * (2 * n - 1)
yield from sub(0)
next(queens(31))
next(queens_lex(31))
#Compare to A065188
|