N-queens problem: Difference between revisions

Content added Content deleted
m (→‎{{header|Phix}}: use pygments)
m (→‎Python: backtracking on permutations: Small speed and readability improvements (Python can handle negative indexes))
Line 12,866: Line 12,866:


<syntaxhighlight lang="python">def queens(n):
<syntaxhighlight lang="python">def queens(n):

⚫
a = list(range(n))
up = [True]*(2*n - 1)
def queen(i):
down = [True]*(2*n - 1)
if i < n:
def sub(i):
⚫
if i == n:
yield tuple(a)
else:
for k in range(i, n):
for k in range(i, n):
j = a[k]
l, j = a[i], a[k]
p = i + j
if b[i + j] and c[i - j]:
q = i - j + n - 1
b[i + j] = c[i - j] = False
if up[p] and down[q]:
a[i], a[k] = j, l
up[p] = down[q] = False
yield from queen(i + 1)
a[i], a[k] = a[k], a[i]
a[i], a[k] = l, j
yield from sub(i + 1)
b[i + j] = c[i - j] = True
⚫
else:
up[p] = down[q] = True
a[i], a[k] = a[k], a[i]
yield a
⚫
yield from sub(0)


⚫
a = list(range(n))
⚫
#Count solutions for n=8:
b = [True] * (2 * n - 1)
c = [True] * (2 * n - 1)
⚫
yield from queen(0)


⚫
# Count solutions for n=8
sum(1 for p in queens(8))
sum(1 for p in queens(8))
92</syntaxhighlight>
92</syntaxhighlight>
Line 12,894: Line 12,895:


<syntaxhighlight lang="python">def queens_lex(n):
<syntaxhighlight lang="python">def queens_lex(n):

a = list(range(n))
up = [True]*(2*n - 1)
def queen(i):
down = [True]*(2*n - 1)
if i < n:
def sub(i):
if i == n:
yield tuple(a)
else:
for k in range(i, n):
for k in range(i, n):
a[i], a[k] = a[k], a[i]
l, j = a[i], a[k]
j = a[i]
a[i], a[k] = j, l
p = i + j
if b[i + j] and c[i - j]:
q = i - j + n - 1
b[i + j] = c[i - j] = False
if up[p] and down[q]:
yield from queen(i + 1)
up[p] = down[q] = False
b[i + j] = c[i - j] = True
yield from sub(i + 1)
a[i:(n - 1)] = a[(i + 1):n]
up[p] = down[q] = True
a[n - 1] = j
x = a[i]
else:
for k in range(i + 1, n):
yield a

a[k - 1] = a[k]
a[n - 1] = x
a = list(range(n))
yield from sub(0)
b = [True] * (2 * n - 1)
c = [True] * (2 * n - 1)
yield from queen(0)



next(queens(31))
next(queens(31))
(0, 2, 4, 1, 3, 8, 10, 12, 14, 6, 17, 21, 26, 28, 25, 27, 24, 30, 7, 5, 29, 15, 13, 11, 9, 18, 22, 19, 23, 16, 20)
[0, 2, 4, 1, 3, 8, 10, 12, 14, 6, 17, 21, 26, 28, 25, 27, 24, 30, 7, 5, 29, 15, 13, 11, 9, 18, 22, 19, 23, 16, 20]


next(queens_lex(31))
next(queens_lex(31))
(0, 2, 4, 1, 3, 8, 10, 12, 14, 5, 17, 22, 25, 27, 30, 24, 26, 29, 6, 16, 28, 13, 9, 7, 19, 11, 15, 18, 21, 23, 20)
[0, 2, 4, 1, 3, 8, 10, 12, 14, 5, 17, 22, 25, 27, 30, 24, 26, 29, 6, 16, 28, 13, 9, 7, 19, 11, 15, 18, 21, 23, 20]


#Compare to A065188
#Compare to A065188
Retrieved from "https://rosettacode.org/wiki/N-queens_problem"