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

 

Logo
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
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
Sequence in context: A007476 A202552 A272301 * A129698 A261134 A117419
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.

License Agreements, Terms of Use, Privacy Policy. .

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