|
Consider an n x n board in which the squares are coloured black and white in the usual chequered fashion and with at least one white corner square. (i) In how many ways can n non-challenging rooks be placed on the white squares? (ii) In how many ways can n non-challenging rooks be placed on the black squares? I've tried some combinations with shading z certain square and deleting the row and the column in which it was and then using recurrence, but it doesn't work. |
||||
|
|
Let $a_n$ denote the number of ways to place $n$ non-challenging rooks on the white squares of the $n \times n$ board. It is easiest to break the analysis into two cases, depending on the parity of $n$. If $n = 2k$ is even, place the rooks column by column. In the first column, there are $k$ white squares available to place a rook. Similarly, in the second column, there are $k$ available white squares to place a rook, since the checkboard pattern prevents a rook in the first column from attacking a rook in the second column if they are the same color square. Now cross out the two rows that contain your rooks (i.e. the positions in the other columns that they attack). You are reduced to placing $n-2$ rooks on an $(n-2) \times (n-2)$ board. So $a_{2k} = k^2 a_{2k-2}$. This recurrence is easily solved (with the initial condition $a_2 = 1$ easily verified) to give $a_n = ((n/2)!)^2$ if $n$ is even. Note that by symmetry, when $n$ is even, $a_n$ also denotes the solution to part (ii). When $n$ is odd, the two problems are no longer symmetric, so must be handled separately. But each can be solved by the same method as in the even case. |
|||
|
|
|
We are looking at all permutations of $n$ that are (white squares case) parity-perserving, or (black square case) parity-inversing. If $n$ is even the black squares case is equivalent to the white square case (by a vertical reflection for instance), and if $n$ is odd the black square case has no solutions (the odd numbers $1,3,\ldots,n$ must map bijectively to fewer even numbers $2,4,\ldots,n-1$). So it remains to do the white square case. But now we must permute the odd and the even numbers independently among themselves, for $\lfloor\frac n2\rfloor!\times\lceil\frac n2\rceil!$ solutions. |
|||
|
|
For odd $n$ there are no such rook placements on the black squares. Label the squares with ordered pairs from $(1,1)$ at the upper left to $(n,n)$ at the lower right. The white squares are now those $(x,y)$ for which $x+y=0 \mod 2$, while the black squares are those $(x,y)$ for which $x+y=1 \mod 2.$ The permutation caused by the rook placement on black squares now has the property that it maps an even to an odd, and an odd to an even. Considering the cycle decomposition of the permutation, we can see that in each cycle we must alternate odd, even, odd, even etc. [note we do not have any one-cycles, i.e. the permutation has no fixed points, since for example a rook at $(5,5)$ is on a white square.] Also the length of each cycle must be even, since we cannot have e.g. the cycle $(a,b,c)$ where each of $a,b$, $b,c$, and $c,a$ have opposite parity. But then since each cycle has even length (and no fixed points), adding the lengths of the cycles gives an even number, which then cannot be $n$ as $n$ is odd. |
|||||||
|
|
This answer is to confirm the above results by a backtracking algorithm that can easily be generalized e.g. to the $n$-queens problem. The principle is extremely simple: place rooks on the board one after another as long as there are no conflicts. Here is the Perl code:
#! /usr/bin/perl -w
#
use warnings;
no warnings 'recursion';
sub search {
my ($n, $black_or_white, $rptr, $count) = @_;
my $current = scalar(@$rptr);
if($current == $n){
$$count++;
for(my $row = 0; $row < $n; $row++){
for(my $col = 0; $col < $n; $col++){
if($rptr->[$col] == $row){
printf " * ";
}
else{
printf " . ";
}
}
printf "\n";
}
printf "\n";
return;
}
my $par = ($black_or_white eq 'black' ? 1 : 0);
for(my $row = ($par+$current)%2; $row < $n; $row += 2){
my $accept = 'yes';
for(my $pos = 0; $pos < $current; $pos++){
if($rptr->[$pos] == $row){
$accept = undef;
last;
}
}
if(defined($accept)){
push @$rptr, $row;
search($n, $black_or_white, $rptr, $count);
pop @$rptr;
}
}
1;
}
MAIN: {
my $n = shift || 4;
if($n<1 || $n !~ /^\d+$/){
print STDERR "integer argument please\n";
exit -1;
}
my @rooks = ();
my $total = 0;
search($n, 'white', \@rooks, \$total);
printf "%d solutions found (%d x %d, white)\n\n",
$total, $n, $n;
$total = 0;
search($n, 'black', \@rooks, \$total);
printf "%d solutions found (%d x %d, black)\n\n",
$total, $n, $n;
exit 0;
}
We can use this to produce a table of values, which confirms the results from the other users.
#! /usr/bin/perl -w
#
my $mx = shift || 12;
for(my $n=1; $n<=$mx; $n++){
my $cmd = "./rooks.pl $n | grep solutions";
system $cmd;
printf "\n";
}
This produces the following table: 1 solutions found (1 x 1, white) 0 solutions found (1 x 1, black) 1 solutions found (2 x 2, white) 1 solutions found (2 x 2, black) 2 solutions found (3 x 3, white) 0 solutions found (3 x 3, black) 4 solutions found (4 x 4, white) 4 solutions found (4 x 4, black) 12 solutions found (5 x 5, white) 0 solutions found (5 x 5, black) 36 solutions found (6 x 6, white) 36 solutions found (6 x 6, black) 144 solutions found (7 x 7, white) 0 solutions found (7 x 7, black) 576 solutions found (8 x 8, white) 576 solutions found (8 x 8, black) 2880 solutions found (9 x 9, white) 0 solutions found (9 x 9, black) 14400 solutions found (10 x 10, white) 14400 solutions found (10 x 10, black) 86400 solutions found (11 x 11, white) 0 solutions found (11 x 11, black) 518400 solutions found (12 x 12, white) 518400 solutions found (12 x 12, black) We can confirm the pattern for odd values (white), which seems to be $$((n-1)/2)!*((n-1)/2+1)!.$$ |
|||
|
|
|
Another interesting challenge that does not produce quite as many answers is where $n$ non-attacking queens are placed on an $n\times n$ board. This gives the following table of values: 1 solutions found (1 x 1) 0 solutions found (2 x 2) 0 solutions found (3 x 3) 2 solutions found (4 x 4) 10 solutions found (5 x 5) 4 solutions found (6 x 6) 40 solutions found (7 x 7) 92 solutions found (8 x 8) 352 solutions found (9 x 9) 724 solutions found (10 x 10) 2680 solutions found (11 x 11) 14200 solutions found (12 x 12) 73712 solutions found (13 x 13) The backtracking algorithm to compute these goes as follows. It is hoped it may serve as a reference as this problem tends to pop up multiple times.
#! /usr/bin/perl -w
#
use warnings;
no warnings 'recursion';
sub search {
my ($n, $qptr, $count) = @_;
my $current = scalar(@$qptr);
if($current == $n){
$$count++;
for(my $row = 0; $row < $n; $row++){
for(my $col = 0; $col < $n; $col++){
if($qptr->[$col] == $row){
printf " * ";
}
else{
printf " . ";
}
}
printf "\n";
}
printf "\n";
return;
}
for(my $row = 0; $row < $n; $row++){
my $accept = 'yes';
for(my $pos = 0; $pos < $current; $pos++){
if($qptr->[$pos] == $row){
$accept = undef;
last;
}
elsif($pos + $qptr->[$pos] == $current + $row){
$accept = undef;
last;
}
elsif($pos - $qptr->[$pos] == $current - $row){
$accept = undef;
last;
}
}
if(defined($accept)){
push @$qptr, $row;
search($n, $qptr, $count);
pop @$qptr;
}
}
1;
}
MAIN: {
my $n = shift || 4;
if($n<1 || $n !~ /^\d+$/){
print STDERR "integer argument please\n";
exit -1;
}
my @queens = ();
my $total = 0;
search($n, \@queens, \$total);
printf "%d solutions found (%d x %d)\n\n",
$total, $n, $n;
exit 0;
}
Build the table with
#! /usr/bin/perl -w
#
my $mx = shift || 12;
for(my $n=1; $n<=$mx; $n++){
my $cmd = "./queens.pl $n | grep solutions";
system $cmd;
printf "\n";
}
|
|||
|
