2
$\begingroup$

I was thinking on some variations of the n-Queen problem until I reached the following problem I couldn't solve:
How many ways are there to put $n$ kings (as in a chess game) on a $n\times n$ chessboard such that no two kings threaten each other?
I'm not so optimistic that it would be solved in "non purely computational" methods. I've tried recursions, bijection and almost anything in my own knowledge yet I have achieved nothing.
Any help would be appreciated!

$\endgroup$
10
  • 1
    $\begingroup$ See oeis.org/A002464 (though there's an additional constraint there, that there be just one king in each row and column). $\endgroup$ Aug 19, 2021 at 15:22
  • $\begingroup$ @BarryCipra I think that's slightly different. $\endgroup$
    – Trebor
    Aug 19, 2021 at 15:24
  • 1
    $\begingroup$ This question does not require that each King be on a different row or column. $\endgroup$
    – Trebor
    Aug 19, 2021 at 15:25
  • $\begingroup$ @Barry Cipra I've seen this sequence before. Actually that was one of my motivations to think of this problem yet with having the additional constraint, having a recursive algorithm would be possible which is not useful here. $\endgroup$
    – Aryan
    Aug 19, 2021 at 15:26
  • 1
    $\begingroup$ oeis.org/A201513 is this specific sequence (at least according to the Kotěšovec book), BTW. $\endgroup$ Aug 19, 2021 at 16:18

1 Answer 1

1
$\begingroup$

Based on the section 2.1.2 book "Non-attacking chess pieces" by "Václav Kotěšovec", the general answer does exist and is equal to the following : $$ \frac{n^{2n}}{n!}\left(1-\frac{9(n-1)n}{2n^2}+\frac{(n-1)n(243n^2-439n-142)}{24n^4}-\ldots\right) $$ enter image description here

$\endgroup$
8
  • $\begingroup$ ...that seems more like an asymptotic estimate than a 'general answer', especially with an apparently infinite series with no general formula for its terms. $\endgroup$ Aug 19, 2021 at 15:56
  • 1
    $\begingroup$ @StevenStadnicki, the series might tacitly terminate if there's a build-up of factors $(n-k)$ in the numerator, culminating in an $n-n$. $\endgroup$ Aug 19, 2021 at 16:00
  • $\begingroup$ @BarryCipra True enough. Without a formula for those messy polynomials I can't imagine proving integrality of the resulting expression, though. Taking $n$ to be some medium-largish prime does not seem likely to yield fruitful results in the numerator. $\endgroup$ Aug 19, 2021 at 16:01
  • $\begingroup$ The discriminant on the quadratic in the third term, for instance, is 330745 = 5 * 29 * 2281; with none of the numbers themselves or that discriminant having particularly nice forms it's really hard to see where those coefficients are coming from. $\endgroup$ Aug 19, 2021 at 16:07
  • 1
    $\begingroup$ I found the book online at kotesovec.cz/books/… $\endgroup$ Aug 19, 2021 at 16:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .