%I #53 Mar 20 2023 19:24:17
%S 1,2,4,9,23,66,204,669,2305,8348,31542,124021,507937,2154494,9455972,
%T 42847307,200258387,962904904,4759773172,24142168317,125575232141,
%U 668689805690,3643481771390,20286338601133
%N 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.
%C Equivalently, a(n) is the number of ways to place non-attacking queens on a right triangular board with n cells on each side.
%C Task was proposed by Yandex, during ICPC NERC 2022-2023, as a side CTF contest.
%C The terms appear to be growing exponentially.
%e a(0) = 1, since there is only the empty board.
%e a(1) = 2, since there are 2 configurations:
%e +---+ +---+
%e | Q | | . |
%e +---+ +---+
%e a(2) = 4
%e +-----+ +-----+ +-----+ +-----+
%e | . # | | Q # | | . # | | . # |
%e | . . | | . . | | Q . | | . Q |
%e +-----+ +-----+ +-----+ +-----+
%e a(3) = 9
%e +-------+
%e | . # # |
%e | . . # |
%e | . . . |
%e +-------+
%e +-------+ +-------+
%e | Q # # | | . # # |
%e | . . # | | Q . # |
%e | . . . | | . . . |
%e +-------+ +-------+
%e +-------+ +-------+
%e | . # # | | . # # |
%e | . . # | | . Q # |
%e | Q . . | | . . . |
%e +-------+ +-------+
%e +-------+ +-------+
%e | . # # | | . # # |
%e | . . # | | . . # |
%e | . Q . | | . . Q |
%e +-------+ +-------+
%e +-------+ +-------+
%e | Q # # | | . # # |
%e | . . # | | Q . # |
%e | . Q . | | . . Q |
%e +-------+ +-------+
%o (Python)
%o bitToIndex = {}
%o indexToBit = {}
%o def addToBoard(board, bit, n):
%o (i, j) = bitToIndex[bit]
%o for k in range(n - j):
%o board |= indexToBit[(k, j)]
%o for k in range(n - i):
%o board |= indexToBit[(i, k)]
%o for k in range(-min(i, j), (n - abs(i - j) + 1) // 2 - min(i, j)):
%o board |= indexToBit[(i + k, j + k)]
%o for k in range(i + j + 1):
%o board |= indexToBit[(k, i + j - k)]
%o return board
%o def r(start, board, n):
%o result = 1
%o for i in range(start, n * (n + 1) // 2):
%o bit = 1 << i
%o if board & bit == 0:
%o newBoard = addToBoard(board, bit, n)
%o result += r(i + 1, newBoard, n)
%o return result
%o # Number of peaceful queens boards in a triangular square grid with size n
%o def a(n):
%o bit = 1
%o for j in range(n):
%o for k in range(n - j):
%o bitToIndex[bit] = (j, k)
%o indexToBit[(j, k)] = bit
%o bit *= 2
%o return r(0, 0, n)
%o for n in range(21):
%o print(a(n))
%Y Cf. A274616, A287227.
%K nonn,more,hard
%O 0,2
%A _Alexander Kuleshov_, Dec 13 2022
%E a(20)-a(23) from _Bert Dobbelaere_, Jan 29 2023