A359032 a(n) is the number of ways to place non-attacking queens on an n X n board with no queens above the main diagonal.

1, 2, 4, 9, 23, 66, 204, 669, 2305, 8348, 31542, 124021, 507937, 2154494, 9455972, 42847307, 200258387, 962904904, 4759773172, 24142168317, 125575232141, 668689805690, 3643481771390, 20286338601133

Offset

0,2

Comments

Equivalently, a(n) is the number of ways to place non-attacking queens on a right triangular board with n cells on each side.

Task was proposed by Yandex, during ICPC NERC 2022-2023, as a side CTF contest.

The terms appear to be growing exponentially.

Links

Table of n, a(n) for n=0..23.

Example

a(0) = 1, since there is only the empty board.
a(1) = 2, since there are 2 configurations:
  +---+  +---+
  | Q |  | . |
  +---+  +---+
a(2) = 4
  +-----+ +-----+ +-----+ +-----+
  | . # | | Q # | | . # | | . # |
  | . . | | . . | | Q . | | . Q |
  +-----+ +-----+ +-----+ +-----+
a(3) = 9
  +-------+
  | . # # |
  | . . # |
  | . . . |
  +-------+
  +-------+  +-------+
  | Q # # |  | . # # |
  | . . # |  | Q . # |
  | . . . |  | . . . |
  +-------+  +-------+
  +-------+  +-------+
  | . # # |  | . # # |
  | . . # |  | . Q # |
  | Q . . |  | . . . |
  +-------+  +-------+
  +-------+  +-------+
  | . # # |  | . # # |
  | . . # |  | . . # |
  | . Q . |  | . . Q |
  +-------+  +-------+
  +-------+  +-------+
  | Q # # |  | . # # |
  | . . # |  | Q . # |
  | . Q . |  | . . Q |
  +-------+  +-------+

Prog

(Python)
bitToIndex = {}
indexToBit = {}
def addToBoard(board, bit, n):
    (i, j) = bitToIndex[bit]
    for k in range(n - j):
        board |= indexToBit[(k, j)]
    for k in range(n - i):
        board |= indexToBit[(i, k)]
    for k in range(-min(i, j), (n - abs(i - j) + 1) // 2 - min(i, j)):
        board |= indexToBit[(i + k, j + k)]
    for k in range(i + j + 1):
        board |= indexToBit[(k, i + j - k)]
    return board
def r(start, board, n):
    result = 1
    for i in range(start, n * (n + 1) // 2):
        bit = 1 << i
        if board & bit == 0:
            newBoard = addToBoard(board, bit, n)
            result += r(i + 1, newBoard, n)
    return result
# Number of peaceful queens boards in a triangular square grid with size n
def a(n):
    bit = 1
    for j in range(n):
        for k in range(n - j):
            bitToIndex[bit] = (j, k)
            indexToBit[(j, k)] = bit
            bit *= 2
    return r(0, 0, n)
for n in range(21):
    print(a(n))

Crossrefs

Cf. A274616, A287227.

Sequence in context: A007476 A202552 A272301 * A129698 A261134 A117419

Adjacent sequences: A359029 A359030 A359031 * A359033 A359034 A359035

Keyword

nonn,more,hard

Author

Alexander Kuleshov, Dec 13 2022

Extensions

a(20)-a(23) from Bert Dobbelaere, Jan 29 2023

Status

approved