OFFSET
1,4
COMMENTS
The length of the n-th row is A000170(n) for n >= 4.
LINKS
Wikipedia, Eight queens puzzle
FORMULA
a(n) = 0 if no solution exists or n = 1.
EXAMPLE
Table T(n,k) reads as follows:
n / k
-------------------------------------------
1 | 0
2 | 0
3 | 0
4 | 10, 13
5 | 10, 13, 36, 44, 50, 69, 75, 83, 106, 109
6 | 186, 346, 373, 533
For a table of 4 by 4 one of the solutions for placing the 4 queens is [(0,1),(1,3),(2,0),(3,2)] and its compact representation is [1, 3, 0, 2],
this resulting representation is a permutation that can be ranked and its rank is 10.
T(1) = [0]
*-*
|Q| Permutation: [0], Rank: 0
*-*
T(2) = [0] because of no solution and n < 4.
T(4) = [10, 13]
0 1 2 3 0 1 2 3
+---------+ +---------+
0 | . Q . . | | . . Q . |
1 | . . . Q | | Q . . . |
2 | Q . . . | | . . . Q |
3 | . . Q . | | . Q . . |
+---------+ +---------+
Permutation: Permutation:
[1, 3, 0, 2] [2, 0, 3, 1]
Rank: 10 Rank: 13
T(6) = [186, 346, 373, 533]:
0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5
+-------------+ +-------------+ +-------------+ +-------------
0 | . Q . . . . | | . . Q . . . | | . . . Q . . | | . . . . Q . |
1 | . . . Q . . | | . . . . . Q | | Q . . . . . | | . . Q . . . |
2 | . . . . . Q | | . Q . . . . | | . . . . Q . | | Q . . . . . |
3 | Q . . . . . | | . . . . Q . | | . Q . . . . | | . . . . . Q |
4 | . . Q . . . | | Q . . . . . | | . . . . . Q | | . . . Q . . |
5 | . . . . Q . | | . . . Q . . | | . . Q . . . | | . Q . . . . |
+-------------+ +-------------+ +-------------+ +-------------+
Permutation: Permutation: Permutation: Permutation:
[1, 3, 5, 0, 2, 4] [2, 5, 1, 4, 0, 3] [3, 0, 4, 1, 5, 2] [4, 2, 0, 5, 3, 1]
Rank:186 Rank:346 Rank: 373 Rank: 533
PROG
(Python)
from sympy.combinatorics import Permutation
def queens(n, i = 0, cols=0, pos_diags=0, neg_diags=0, sol=None):
if sol is None: sol = []
if i == n: yield sol[:]
else:
neg_diag_mask_ = 1 << (i+n)
col_mask = 1
for j in range(n):
col_mask <<= 1
pos_diag_mask = col_mask << i
neg_diag_mask = neg_diag_mask_ >> (j+1)
if not (cols & col_mask or pos_diags & pos_diag_mask or neg_diags &
neg_diag_mask):
sol.append(j)
yield from queens(n, i + 1,
cols | col_mask,
pos_diags | pos_diag_mask,
neg_diags | neg_diag_mask,
sol)
sol.pop()
row = lambda n: [Permutation(sol).rank() for sol in queens(n)] if n >= 4 else [0]
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Darío Clavijo, Nov 28 2024
STATUS
approved