# How many different ways can we place 4 identical rooks on the following chess board

How many different ways can we place 4 identical rooks on the following chess board so that no two of them attack each other?

I know when the board is $n \times n$ and we have $n$ towers then the solution is simply $n!$

However I am not sure how to solve the problem in this case.

There is probably a more clever way to solve it, but I would largely brute force this, where the only 'clever' thing I can think of is to note that we have 4 different column sizes: 2,4,6, and 8. So, call these column types 'A', 'B', 'C', and 'D'. Now, for example, suppose we have rooks in column types A,B,C, and D. Those can be placed in 2*(4-1)(6-2)(8-3)=2*3*4*5 ways (always place them starting with the shorter columns). Moreover, since there are 2 'A' columns, 2 'B' columns, 2 'C' columns, and 1 'D' column, we can multiply this by 2*2*2*1=8

OK, so let this be the 'ABCD' entry in a table that lists all column type combination, and how many specific boards there will be for that combination (2*3*4*5*8 in that case). So here is what I ge

AABB: 2*1*2*1*1

AABC: 2*1*2*3*4

AABD: 2*1*2*5*2

AACD: 2*1*4*5*2

AACC: 2*1*4*3*1

ABBC: 2*3*2*3*4

ABBD: 2*3*2*5*2

ABCC: 2*3*4*3*4

ABCD: 2*3*4*5*8

ACCD: 2*5*4*5*2

BBCC: 4*3*4*3*1

BBCD: 4*3*4*5*2

BCCD: 4*5*4*5*2

OK, so multiply all those and add them up!

Just to verify that Bram28's answer is correct, we can count it up by building the graph whose 32 vertices are the positions on the board, with edges for rook attacks. Then count the number of independent sets of size four.

Here's Sage code to do that:

from sage.graphs.independent_sets import IndependentSets

posns = [(x,y) for x in range(7) for y in range(max(3-x,x-3),min(5+x,11-x))]
def isedge(a,b):
return (a[0]==b[0]) != (a[1]==b[1])
G = Graph([posns, isedge])
print(sum(len(x) == 4 for x in IndependentSets(G)))


And here it is on SageCell. The answer 3532 agrees with Bram28's enumeration.

• @Kundor. Thanks for verifying! I would have put good money on having made a mistake somewhere ... :) – Bram28 May 23 '17 at 22:39