In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?

Solution 1:

The complete answer to this question is contained in the Knights polynomials. By definition, the coefficient of $q^k$ in the $m\times n$ knights polynomial, $K_{m,n}(q)$, is the number of ways that $k$ non-attacking knights can be placed on an $m\times n$ board. Of course, it's a tautology to say that this solves the problem, but there is an algorithm to compute them. Using this algorithm, the first six $m\times n$ knights polynomials (per your request) are

\begin{align} K_{1,1}(q) &= q+1 \\ K_{2,2}(q) &= q^4+4 q^3+6 q^2+4 q+1 \\ K_{3,3}(q) &= 2 q^5+18 q^4+36 q^3+28 q^2+9 q+1\\ K_{4,4}(q) &= 6 q^8+48 q^7+170 q^6+340 q^5+412 q^4+276 q^3+96 q^2+16 q+1\\ K_{5,5}(q) &= q^{13}+15 q^{12}+158 q^{11}+994 q^{10}+3679 q^9+8526 q^8+12996 q^7+13384 q^6 \\ &+ \; 9386 q^5+4436 q^4+1360 q^3+252 q^2+25 q+1\\ K_{6,6}(q) &= 2 q^{18}+40 q^{17}+393 q^{16}+2560 q^{15}+12488 q^{14}+47684 q^{13}+141969 q^{12} \\ &+ \; 323476 q^{11}+556274 q^{10}+716804 q^9+688946 q^8+491140 q^7+257318 q^6 \\ &+ \; 97580 q^5+26133 q^4+4752 q^3+550 q^2+36 q+1 \end{align}

Note that these polynomials agree with the results that you provide. For example, the coefficient of $q^{15}$ in $K_{6,6}$ is 2560, corresponding to your statement that $M=6,N=15 \Rightarrow \text{ans} =2560$. The coefficients of $q^2$ also agree with this OEIS sequence.

The algorithm to compute these is very similar to the obviously related Kings problem. Neil Calkin and his REU students provide a very thorough analysis of that problem in two papers in Congressus Numerantium. Shaina Race has a publicly accessible presentation of their results here. I published a paper presenting an implementation of the algorithm in Mathematica V5. The technique for counting knights is a bit more complicated but uses very similar ideas. Unfortunately, I've been able to compute the $7\times 7$ knights polynomial but my computer chokes on $8\times 8$, the size of an actual chess board.

Solution 2:

Firstly, see OEIS for a list of numbers. E.g. Sequence A172132 counts the number of ways to place 2 nonattacking knights on an $n\times n$ board. Note this site should be among the first ones (besides Google) which you should visit when you have a combinatorial problem (like counting).

Secondly, I don't have a "closed formula" for this problem, but an algorithm which should work for the given input limits. Since the problem is of quite an ACM/ICPC nature, I would assume you'd be satisfied with an algorithm which (when implemented correctly) would give the answer in reasonable time.

My algorithm is dynamic programming (Some prefer "recursion" because no optimization is involved. I don't distinguish them here.).

Let $f[i,j,v_{last},v_{second\_last}]$ denote the number of ways to place $j$ non-attacking knights in the first $i$ rows of the $n\times n$ board with the last and the second last rows having the states denoted by $v_{last}$ and $v_{second\_last}$. Those are two bit-vectors, with 1 being a knight. So a row with two knights in the 2nd and 5th cell when $n=5$ will be denoted as 01001.

So the most important part would be the equation (state transition equation) $$ f[i,j,v_{last},v_{second\_last}] = \sum_{v_{third\_last}}f[i-1,j-\operatorname{popcount}(v_{last}),v_{second\_last},v_{third\_last}] $$ where $\operatorname{popcount}(v)$ is the number of 1's in bit-vector $v$. Note the three vectors must be consistent (non-attacking).

There're then $N M 2^{2M}$ states, and the transition takes another $2^M$ time, so the algorithm (if implemented properly) has a time complexity of $O(N M 2^{3M})$. The bound is not tight, since there're many invalid combinations of vectors.