1
$\begingroup$

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

enter image description here

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.

$\endgroup$
2
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

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

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.