

A359032


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


0



1, 2, 4, 9, 23, 66, 204, 669, 2305, 8348, 31542, 124021, 507937, 2154494, 9455972, 42847307, 200258387, 962904904, 4759773172, 24142168317, 125575232141, 668689805690, 3643481771390, 20286338601133
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Equivalently, a(n) is the number of ways to place nonattacking queens on a right triangular board with n cells on each side.
Task was proposed by Yandex, during ICPC NERC 20222023, as a side CTF contest.
The terms appear to be growing exponentially.


LINKS



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



KEYWORD

nonn,more,hard


AUTHOR



EXTENSIONS



STATUS

approved



