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

Author

Alexander Kuleshov, Dec 13 2022

Keywords

• nonn
• more
• hard

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.

Examples

			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 |
  +-------+  +-------+
		

Crossrefs

Cf. A274616, A287227.

Programs

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))

Extensions

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