Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given $N,M$ with $1 \le M \le 6$ and $1\le N \le 36$. In how many ways we can place $N$ knights (mutually non-attacking) on an $M \times M$ chessboard?

For example:

$M = 2, N = 2$, ans $= 6$
$M = 3, N = 2$, ans $ = 28$
$M = 6, N = 15$, ans $= 2560$

It is possible to solve this using graph theory. However, I am (more) interested in a combinatorial approach (A closed form solution).

Similar problem

share|improve this question
5  
Do you mean that they are to be mutually non-attacking? –  Brian M. Scott Feb 15 '13 at 15:34
    
Clearly the answer is $M^2$ choose $N$. What does graph theory have to do with it? –  Chris Eagle Feb 15 '13 at 15:36
    
@Chris Eagle: I don't think that $\choose{{M^2},{N}}$ is giving the right answer. –  user62427 Feb 15 '13 at 15:42
3  
Ummm, you do realize graph theory is combinatorial, don't you? –  Thomas Andrews Feb 15 '13 at 15:43
    
@user62427 I think Chris was answering the question before the "non-attacking" condition was added. –  Thomas Andrews Feb 15 '13 at 15:46

2 Answers 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.

share|improve this answer
    
+1 for the OEIS reference. –  Mark McClure Jul 3 '13 at 12:14

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.