A378488 Table T(n,k) read by rows where in the n-th row the k-th column is the permutation rank of the k-th solution to the n-queens problem in a n X n board.

0, 0, 0, 10, 13, 10, 13, 36, 44, 50, 69, 75, 83, 106, 109, 186, 346, 373, 533, 186, 346, 373, 533, 980, 1032, 1090, 1108, 1188, 1244, 1399, 1515, 1519, 1905, 1956, 2074, 2090, 2197, 2210, 2390, 2649, 2829, 2842, 2949, 2965, 3083, 3134, 3520, 3524, 3640, 3795, 3851

Offset

1,4

Comments

The length of the n-th row is A000170(n) for n >= 4.

Links

Table of n, a(n) for n=1..51.

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

Cf. A000170.

Sequence in context: A248336 A332478 A144814 * A241174 A092887 A131365

Adjacent sequences: A378485 A378486 A378487 * A378489 A378490 A378491

Keyword

nonn,tabf

Author

Darío Clavijo, Nov 28 2024

Status

approved