editing

proposed

row = lambda n: [Permutation(sol).rank() for sol in queens(n)] if n >= 4 else [[1, 0, 0][n-1]]

proposed

editing

editing

proposed

allocated for Darío Clavijo

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

1,4

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

Wikipedia, <a href="https://en.wikipedia.org/wiki/Eight_queens_puzzle">Eight queens puzzle</a>

a(n) = 0 if no solution exists or n = 1.

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

(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 [[1, 0, 0][n-1]]

Cf. A000170.

allocated

nonn,tabf

Darío Clavijo, Nov 28 2024

approved

editing

allocated for Darío Clavijo

allocated

approved

editing

proposed

editing

proposed

a(n) >= A060594(n) for n >= 4.

Cf. A000079, A000217, A036289, A060594, A373749.

proposed

editing

editing

proposed

a(n) is the cumulative bit XOR of the bits in the binary representation of n.

In the binary representation of n read from the most to least significant bit order then perform a cumulative XOR and store from least to most significant bit order.