A regular King in a chess board can attack all its adjacent 8 cells (vertical, horizontal or diagonal). Now you are given a $10 \times n$ chessboard, your task is to place exactly two kings in each column such that no king attacks another. What is the number of ways to do that?


I can count that in column A we can place two non attacking kings in $36$ ways.

  • $\begingroup$ What work have you done on it so far? $\endgroup$ – Null Dec 15 '14 at 5:36
  • $\begingroup$ i can count that in A collumn we can place two non attacking kings in 36 ways $\endgroup$ – annonymus Dec 15 '14 at 5:37
  • $\begingroup$ Okay, you should add any work you've done to your question. $\endgroup$ – Null Dec 15 '14 at 5:38
  • $\begingroup$ what work , i've added ! in my last comment $\endgroup$ – annonymus Dec 15 '14 at 5:42
  • $\begingroup$ Please edit your question with the work you've indicated in your comment. It should be part of the question, not hidden in a comment to the question. $\endgroup$ – Null Dec 15 '14 at 5:45

It's the number of walks of length $n$ in the graph:

enter image description here

We draw an edge between $(a,b)$ and $(c,d)$ if a column with kings in rows $a$ and $b$ can be placed next to a column with kings in rows $c$ and $d$.

So, the number could be computed by taking powers of its adjacency matrix and summing the entries.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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