# Number of ways to place exactly two kings in each column such that no king attacks another

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?

### Progress

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

• What work have you done on it so far? – Null Dec 15 '14 at 5:36
• i can count that in A collumn we can place two non attacking kings in 36 ways – annonymus Dec 15 '14 at 5:37
• Okay, you should add any work you've done to your question. – Null Dec 15 '14 at 5:38
• what work , i've added ! in my last comment – annonymus Dec 15 '14 at 5:42
• 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. – Null Dec 15 '14 at 5:45

It's the number of walks of length $n$ in the graph:
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$.