[bushindo]

The following questions assume a 8x8 chess board. Starting with an empty chess board,

1) How many different ways can you place 8 rooks so that none can attack another?

2) how many different ways can you place 8 bishops so that none can attack another?

Edited June 3, 2009 by bushindo

[bushindo]

22,522,960

Here's how I figured (writing a small program to solve)...

Number the squares from 1 to 64, starting from top-left, row-by-row.

Use a rule that every new bishop must be placed at a higher number than the last.

If you successfully place all 8 bishops without contention, increment a counter.

The first bishop, b1, will be in the range 1..57,

The second bishop, b2, will be in the range b1..58,

...

The eighth bishop, b8, will be in the range b7..64

A simple subroutine evaluates whether a square (represented by number) is reachable by any bishops currently on the board. The rest is just a bunch of nested loops with the counter in the inner-most loop.

I'm including the source code (in case there's a bug in either my logic or the code). It's zero-based numbering for the board, but otherwise matches the description above.

use strict;

sub intersect {
my ($p2, @pn)=@_;
my $p1;
foreach $p1 (@pn) {
return 1 if (($p2-$p1)%7==0) && ($p1%8 > $p2%8);
return 1 if (($p2-$p1)%9==0) && ($p1%8 < $p2%8);
}
return 0;
}

sub count_patterns {
my ($b0, $b1, $b2, $b3, $b4, $b5, $b6, $b7, $patterns)=(0,0,0,0,0,0,0,0,0);
for ($b0=0; $b0<57; $b0++) {
for ($b1=1+$b0; $b1<58; $b1++) {
next if intersect($b1, $b0);
for ($b2=1+$b1; $b2<59; $b2++) {
next if intersect($b2, $b0, $b1);
for ($b3=1+$b2; $b3<60; $b3++) {
next if intersect($b3, $b0, $b1, $b2);
for ($b4=1+$b3; $b4<61; $b4++) {
next if intersect($b4, $b0, $b1, $b2, $b3);
for ($b5=1+$b4; $b5<62; $b5++) {
next if intersect($b5, $b0, $b1, $b2, $b3, $b4);
for ($b6=1+$b5; $b6<63; $b6++) {
next if intersect($b6, $b0, $b1, $b2, $b3, $b4, $b5);
for ($b7=1+$b6; $b7<64; $b7++) {
next if intersect($b7, $b0, $b1, $b2, $b3, $b4, $b5, $b6);
$patterns++;
}
}
}
}
}
}
}
print "$b0 : patterns=$patterns\n";
}
return $patterns;
}

count_patterns;

#! /usr/bin/perl

This logic checks out for me. I verified that the code does examine all the possible ₆₄C₈ = 4426165368 bishop placements. The subroutine that checks for attack lines seems to be correctly used. Unless someone contests this, I declare Phatfinger's the most satisfactory.

Well done, Phatfinger. Adding the bishop one at a time and using next is much more optimal than generating 8 placement locations and check them for conflict.

Edited June 6, 2009 by bushindo

[Guest]

This logic checks out for me. I verified that the code does examine all the possible ₆₄C₈ = 4426165368 bishop placements. The subroutine that checks for attack lines seems to be correctly used. Unless someone contests this, I declare Phatfinger's the most satisfactory.

Well done, Phatfinger. Adding the bishop one at a time and using next is much more optimal than generating 8 placement locations and check them for conflict.

I'm not contesting, but how did you get 4,426,165,368 using his program, while he got 22,522,960? Did you do something different than what he did?

[Guest]

I think you made a program to solve for thisThat solves for how many ways 14 bishops can be placed without attacking.

Thats where I got that number in my last post #23....I just am not sure if what I did is the correct way to get the other number I put up.

I take it you ran the calculated result through a search engine and found what other sites publish the same result? That's not a bad way to verify the answer! If you follow the link on that same page to, "Solution to the n-Bishops problem of trying to place n identical bishops on an n x n chessboard," then you'll see the same series (where n is passed in as a parameter). Where n=8, the solution I presented matches that same value.

[Guest]

I think you made a program to solve for thisThat solves for how many ways 14 bishops can be placed without attacking.

Thats where I got that number in my last post #23....I just am not sure if what I did is the correct way to get the other number I put up.

James8421, I thought it was weird that numbers from this series would exactly match the "Number of placements of 2n-2 nonattacking bishops on an n X n board." page. It turns out they don't. I think that the page you referenced is mislabeled-- the math doesn't match up. There should be only 256 placements of 14 non-attacking bishops on an 8 x 8 board.

[Guest]

James8421, I thought it was weird that numbers from this series would exactly match the "Number of placements of 2n-2 nonattacking bishops on an n X n board." page. It turns out they don't. I think that the page you referenced is mislabeled-- the math doesn't match up. There should be only 256 placements of 14 non-attacking bishops on an 8 x 8 board.

Ok try this site. This is where I originally was looking to see if there was some sort of formula to solve this problem. Unfortunatly I did not find one, but from this site is where I found the other one. (you'll see when you go there). It seems to still confirm the 22,522,960 as the number of ways to place 14 bishops on an 8x8 board. Also there is a formula on that site to find the maximum distinct ways of placing 14 bishops.(at least I think anyway, could be wrong) If I followed it correctly I get 264 distinct ways of placing 14 bishops. Maybe I am not getting something, I don't know. BTW, what is the answer anyway? Is it 22,522,960, or is it the number Bushindo got? 4,426,165,368 seems too high to me. Either way I don't know, but check it out see what sense you make of it, I could be missing something, thats just what I make of it.

[Guest]

Ok try this site. This is where I originally was looking to see if there was some sort of formula to solve this problem. Unfortunatly I did not find one, but from this site is where I found the other one. (you'll see when you go there). It seems to still confirm the 22,522,960 as the number of ways to place 14 bishops on an 8x8 board. Also there is a formula on that site to find the maximum distinct ways of placing 14 bishops.(at least I think anyway, could be wrong) If I followed it correctly I get 264 distinct ways of placing 14 bishops. Maybe I am not getting something, I don't know. BTW, what is the answer anyway? Is it 22,522,960, or is it the number Bushindo got? 4,426,165,368 seems too high to me. Either way I don't know, but check it out see what sense you make of it, I could be missing something, thats just what I make of it.

I think that page is also in error. Although I had to resort to brute force for the 8 bishops in an 8 x 8 board, I find the 14 bishops on an 8x8 board much easier to understand and reduce. It's a fun one, because the formulas are small and you can tie each part to some physical aspect of the board.

Your 2n-2 formula could be tied to the diagonal rows stretching upwards from column A plus the diagonal rows stretching upward from row 4 (which overlap at square A4). Together, those would cover all possible upward diagonal strips. Column A and Row 4 are each of length "n", and overlap at the square A4, so you'd subtract 1 to cover all possible upward diagonal strips to make 2n-1. Since a bishop can't be in the A1 strip (one square wide) without attacking the D4 strip (also one square wide), they're mutually exclusive-- you'll need to subtract one more, so your formula becomes 2n-2... assuming you can arrange one bishop in each of the remaining strips without attacking another at the downward angle.

Finding the arrangements is easier than it first appears, provided you accept that each bishop resides only at the perimeter of the square. I've yet to see anyone articulate a proof for that, but it makes a rough sense to me. If 14 bishops saturate the perimeter of an 8x8 board so that no other bishop can be placed at the perimeter, then moving any bishop into any inner square would threaten four perimeter squares when it could threaten at most three (counting itself) from the perimeter.

Given that perspective, there's a very elegant outcome... except for the corners of the board, each strip described two paragraphs above has only a left and right placement (recalling that the inner placements are deemed unusable), and a companion strip on the board that is its mirror along the diagonal. A left placement in the top left strip will force a right placement in the bottom right strip and vice-versa. For example, the strip (A3,B2,C1) mirrors (F8,G7,H6). Along those two strips ALL SOLUTIONS will include either (A3 and H6) or (C1 and F8).

Examining each of the 14 bishops placed in those 15 strips, you will always have exactly ONE OF EACH of the following, for all possible combos:

1. A1 or H8

2. A8 or H1

3. (A2,H7) or (B1,G8)

4. (A3,H6) or (C1,F8)

5. (A4,H5) or (D1,E8)

6. (A5,H4) or (E1,D8)

7. (A6,H3) or (F1,C8)

8. (A7,H2) or (G1,B8)

Mathematically, all possible arrangements above evaluate to 2^8=256 (or more generically, 2^n).