A348129
Number T(n,k) of ways to place k nonattacking queens on an n X n board; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
Original entry on oeis.org
1, 1, 1, 1, 4, 0, 1, 9, 8, 0, 1, 16, 44, 24, 2, 1, 25, 140, 204, 82, 10, 1, 36, 340, 1024, 982, 248, 4, 1, 49, 700, 3628, 7002, 4618, 832, 40, 1, 64, 1288, 10320, 34568, 46736, 22708, 3192, 92, 1, 81, 2184, 25096, 131248, 310496, 312956, 119180, 13848, 352, 1, 100, 3480, 54400, 412596, 1535440, 2716096, 2119176, 636524, 56832, 724
Offset: 0
T(3,2) = 8:
.-----. .-----. .-----. .-----. .-----. .-----. .-----. .-----.
|Q . .| |Q . .| |. . Q| |. . Q| |. . .| |. Q .| |. Q .| |. . .|
|. . Q| |. . .| |. . .| |Q . .| |Q . .| |. . .| |. . .| |. . Q|
|. . .| |. Q .| |. Q .| |. . .| |. . Q| |. . Q| |Q . .| |Q . .|
`-----´ `-----´ `-----´ `-----´ `-----´ `-----´ `-----´ `-----´.
Triangle T(n,k) begins:
1;
1, 1;
1, 4, 0;
1, 9, 8, 0;
1, 16, 44, 24, 2;
1, 25, 140, 204, 82, 10;
1, 36, 340, 1024, 982, 248, 4;
1, 49, 700, 3628, 7002, 4618, 832, 40;
1, 64, 1288, 10320, 34568, 46736, 22708, 3192, 92;
1, 81, 2184, 25096, 131248, 310496, 312956, 119180, 13848, 352;
...
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.
Original entry on oeis.org
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
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 |
+-------+ +-------+
-
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))
Showing 1-2 of 2 results.
Comments