login
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

%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