The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified February 24 21:21 EST 2024. Contains 370307 sequences. (Running on oeis4.)