N-queens problem: Difference between revisions
m
→Python: Backtracking on permutations: Restored the original look
m (→Python: Backtracking on permutations: Restored the original look) |
|||
(16 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,828 ⟶ 12,829:
print(list(enumerate(first_answer, start=1)))</syntaxhighlight>
===Python:
The following program is a translation of Niklaus Wirth's solution into the Python programming language, but does without the index arithmetic used in the original and uses simple lists instead, which means that the array ''x'' for recording the solution can be omitted. A generator replaces the procedure (see [https://www.inf.ethz.ch/personal/wirth/
<syntaxhighlight lang="python">def queens(n: int, i: int, a: list, b: list, c: list):
if i < n:
Line 12,841 ⟶ 12,842:
for solution in queens(8, 0, [], [], []):
print(solution)</syntaxhighlight>
The algorithm can be
<syntaxhighlight lang="python">def queens(
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:
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
|