This worksheet shows how to use maple to compute rook polynomials. The boards use "matrix notation".

>

> with(combinat):

Warning, the protected name Chi has been redefined and unprotected

>

>

> rook_attack:=proc(L1,L2,n)
#returns true of the rook at L1 attacks
#the rook at L2 on an nxn board
local i,j,ans;
if L1[1]=L2[1] then RETURN(`true`); fi:
if L1[2]=L2[2] then RETURN(`true`); fi:
RETURN(`false`):
end;

>

> array_board:=proc(F,n)
#returns the 0,`x` matrix of the
#forbidden squares from F on an nxn board
local i,j,A;
A:=array(1..n,1..n):
for i from 1 to n do
for j from 1 to n do
A[i,j]:=0;
if member([i,j],F) then A[i,j]:=`x`; fi;
od;
od;
print(A);
end;

>

> array_rooks:=proc(L,n)
#returns the 0,`R` matrix of the rooks at L
#on an nxn board
local i,j,A;
A:=array(1..n,1..n):
for i from 1 to n do
for j from 1 to n do
A[i,j]:=0;
if member([i,j],L) then A[i,j]:=`R`; fi;
od;
od;
print(A);
end;

>

> complement_board:=proc(F,n)
#computes the list of allows squares
#where F is the list of forbidden squares
local i,j,x,L;
L:=[];
for i from 1 to n do
for j from 1 to n do
if not(member([i,j],F)) then L:=[op(L),[i,j]]: fi;
od;
od;
RETURN(L);
end;

>

> non_attacking_rooks_pos:=proc(F,k,n)
#returns all possible positions
#for k non-attacking rooks
#on an nxn board with forbidden positions
#listed in (the list of lists) F
local i,j,ans,cols,R,pos,F0,F1,F2,m,P,x,stop0,is;
P:=permute(n,n);
F0:=F;
pos:=[];
if k=1 then RETURN(complement_board(F0,n)); fi;
for x in P do
stop0:=0;
R:=choose(n,k);
for is in R do
stop0:=0;
for i in is do
if member([i,x[i]],F0) then stop0:=1; fi;
od;
if stop0=0 then pos:=[op(pos),[seq([i,x[i]],i=is)]]; fi;
od;
od;
RETURN(convert(convert(pos,set),list));
end;

>

> rook_polynomial:=proc(F,n,x)
#returns the rook polynomial of the nxn
#board with forbidden positions F
#written as a list of lists of coordinated for
#the forbidden squares
local i,a,p;
p:=1+add(nops(non_attacking_rooks_pos(F,i,n))*x^i,i=1..n);
RETURN(p);
end;

>

Here's the board, with a rook at (1,1) and (2,3).

> array_rooks([[1,1],[2,3]],5);

Does the rook at (1,1) attack the rook at (2,3)?

> rook_attack([1,1],[2,3],5);
rook_attack([1,1],[1,3],5);

>

>

Here's the list of positions where there isn't a rook.

> complement_board([[1,1],[2,3]],3);

Here's an example. All the x'ed out positions mean that the corresponding position is "forbidden" - no rook can land or cross over it. What is the rook polynomial of this board with forbidden positions?

> B:=[[1,1],[1,2],[1,3],[1,4],[2,1],[2,2],[2,3],[2,5],[3,4],[4,3],[4,5],[5,1],[5,2],[5,3],[5,4],[5,5]];
L:=non_attacking_rooks_pos(B,2,5):
nops(L);
array_board(B,5);
rook_polynomial(B,5,x);

>

>

Here's another example. All the x'ed out positions mean that the corresponding position is "forbidden" - no rook can land or cross over it. What is the list of all possible ways 5 non-attacking rooks can be placed on this board with forbidden positions? We only list the first four.

> array_board([[1,2],[1,3],[2,1],[2,3],[3,2],[3,4],[3,5],[5,4]],5);
rook_polynomial([[1,2],[1,3],[2,1],[2,3],[3,2],[3,4],[3,5],[5,4]],5,x);
L:=non_attacking_rooks_pos([[1,2],[1,3],[2,1],[2,3],[3,2],[3,4],[3,5],[5,4]],5,5):
nops(L);
for i from 1 to 4 do
array_rooks(L[i],5);
od;

>

What about the rook polynomials of the 2x2, 3x3, and 4x4 boards with no forbidden positions?

> rook_polynomial([],2,x);
rook_polynomial([],3,x);
rook_polynomial([],4,x);

>

>

>

>