N-queens problem: Difference between revisions
m
→Python: Backtracking on permutations: Restored the original look
m (→Python: Niklaus Wirth algorithm: Added a more optimized version.) |
m (→Python: Backtracking on permutations: Restored the original look) |
||
| (13 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,841 ⟶ 12,842:
for solution in queens(8, 0, [], [], []):
print(solution)</syntaxhighlight>
The algorithm can be
<syntaxhighlight lang="python">def queens(i: int, a: set
if a: # set a is not empty
for j in a:
if i + j not in b and i - j not in c:
yield from queens(i + 1, a - {j})
b.remove(i + j); c.remove(i - j); x.pop()
else:
yield x
for solution in queens(0, set(range(8))):
print(solution)</syntaxhighlight>
===Python: Backtracking on permutations===
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
| |||