bushindo Posted June 3, 2009 Report Share Posted June 3, 2009 (edited) 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 Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 3, 2009 Report Share Posted June 3, 2009 8! ways .... 8 rows .. each row 1 rook in a unique column... first rook 8 places ... second rook 7 places ... and so on Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 3, 2009 Report Share Posted June 3, 2009 hey i have assumed that each rook can attack another ... or is it that, there are only two kinds of rooks black and white, and black can attack only white.??? Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 3, 2009 Report Share Posted June 3, 2009 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? "So that none can attack another"--- do you mean, there is no one in their attack range. OR There is some one in their attack range but killing that rook would result in being killed by another rook, so effectively they "cant" attack anyone. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 3, 2009 Report Share Posted June 3, 2009 (edited) "So that none can attack another"--- do you mean, there is no one in their attack range. OR There is some one in their attack range but killing that rook would result in being killed by another rook, so effectively they "cant" attack anyone. I think he means that when you place the 8 pieces; on the next move none can attack one another. So if you have a rook on square A5, you can't have one on square B5,C5,D5,E5...(In the same setting that is) It's 8!, or 40,320. I'll say 260 ways. If thats right I'll explain. If it's wrong then I won't bother. Edited June 3, 2009 by James8421 Quote Link to comment Share on other sites More sharing options...
0 bonanova Posted June 3, 2009 Report Share Posted June 3, 2009 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? Counting symmetries? Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 3, 2009 Report Share Posted June 3, 2009 (edited) 1) 8! 2) 64*(64-8)*(64-2*8)*(64-3*8)*(64-4*8)*(64-5*8)*(64-6*8)*(64-7*8) = 676,457,349,120 ways Edited June 3, 2009 by adiace Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 3, 2009 Report Share Posted June 3, 2009 (edited) Rotate the chessboard around by 45 degrees and treat it the same as the Rooks 8!=40320 Follow the chessboard from corner to corner and their are 14 diagonals which the bishops can go in. The first diagonal only has one square so only one space for a bishop The second diagonal only has two squares so two places for a bishop The third diagonal has 3 squares but one is diagonal to the first bishop so again only two spaces for a bishop The fourth diagonal has 4 squares and one of them is diagonal to the second bishop The fifth diagonal has 5 squares and two of them are diagonal to the third and first bishops Carry on going along the diagonals and you get the sum below 1*2*2*3*3*4*4*5*3*3*2*2*1=103680 Is this right? Doh i was using as many bishops as possiable Edited June 3, 2009 by Mad Twit Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 3, 2009 Report Share Posted June 3, 2009 Whoops You can have a maximum of 13 bishops which cant attack each other and their are this many different combinations where you can place them Use the method that i used in my above post 1*2*2*3*3*4*4*5*3*3*2*2*1=103680 Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 3, 2009 Report Share Posted June 3, 2009 Whoops You can have a maximum of 13 bishops which cant attack each other and their are this many different combinations where you can place them Use the method that i used in my above post 1*2*2*3*3*4*4*5*3*3*2*2*1=103680 Can't 14 bishops be placed on an 8x8 board where they can't attack each other? nXn board=8x8...n=8 2n-2=B....2*8-2=14 Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 3, 2009 Report Share Posted June 3, 2009 (edited) Arrgggg! another mistake sorry Edited June 3, 2009 by Mad Twit Quote Link to comment Share on other sites More sharing options...
0 bushindo Posted June 3, 2009 Author Report Share Posted June 3, 2009 1) 8! 2) 64*(64-8)*(64-2*8)*(64-3*8)*(64-4*8)*(64-5*8)*(64-6*8)*(64-7*8) = 676,457,349,120 ways For the bishop, you're assuming that each placement of the bishop takes out 8 possible spaces on the board. However, depending on location on the board, bishops take out more than those. Consider the first placement. If the bishop is placed in the center of the board, let say at position (4,4), it would remove 14 positions from the board. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 3, 2009 Report Share Posted June 3, 2009 (edited) 8 rooks 14 bishops. Wow, bushindo, I see I'm way off for the bishops, I agree with you. Edited June 3, 2009 by smata Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 3, 2009 Report Share Posted June 3, 2009 For the bishop, you're assuming that each placement of the bishop takes out 8 possible spaces on the board. However, depending on location on the board, bishops take out more than those. Consider the first placement. If the bishop is placed in the center of the board, let say at position (4,4), it would remove 14 positions from the board. ya.. it hit me as soon as i posted it.. by the way if bishops were to dominate a board, i.e. 8 B's placed such a way that they cover the whole board.. there are 1146 ways to do it. Tried very hard to formulate it, haven't found the time.. but every time i think i am close i find a way to disprove it. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 3, 2009 Report Share Posted June 3, 2009 ya.. it hit me as soon as i posted it.. by the way if bishops were to dominate a board, i.e. 8 B's placed such a way that they cover the whole board.. there are 1146 11664 ways to do it. Tried very hard to formulate it, haven't found the time.. but every time i think i am close i find a way to disprove it. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 3, 2009 Report Share Posted June 3, 2009 I saw the Domination set up too, but it fails in quite a few scenarios acording to the OP, in that they cannot attack one another. It was pretty neat tho. At first made me think there were less than the 11,664 ways, but then those 11,664 ways do not include the scenarios when the board is not dominated, such as lining all the bishops in a single column or row. If one could figure out how many scenarios to take out of the 11,664, and which ones to add back to it, then hey they might be onto something. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 4, 2009 Report Share Posted June 4, 2009 5,337,446,400 ways. This is a great number which I hadn't expected. So it may be wrong ??? Quote Link to comment Share on other sites More sharing options...
0 bushindo Posted June 4, 2009 Author Report Share Posted June 4, 2009 5,337,446,400 ways. This is a great number which I hadn't expected. So it may be wrong ??? Did you count symmetries, and did you make sure not to count the order of placement (order is not important)?. This problem should have a large number of solutions, since 8 isn't the maximum number of bishops you can put on the board. The max is 13 or 14, i think. I haven't worked a solution out completely, but maybe post your solution and we'll evaluate the logic? Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 4, 2009 Report Share Posted June 4, 2009 84,934,656? Is that getting closer? Quote Link to comment Share on other sites More sharing options...
0 bushindo Posted June 4, 2009 Author Report Share Posted June 4, 2009 (edited) 84,934,656? Is that getting closer? Very close. I have a ballpark estimate, and it's pretty close to yours. How did you do that? Edited June 4, 2009 by bushindo Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 4, 2009 Report Share Posted June 4, 2009 I tried figuring out a 4x4 board with 4 bishops, and got 96 ways, and went 96^4....But wasn't sure if I got all the ways for the 4x4, 4 bishop way...I pretty much did it on paper, and it was hard to keep track. Not to sure if thats what should be done, but thats how I got that number. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 5, 2009 Report Share Posted June 5, 2009 Did you count symmetries, and did you make sure not to count the order of placement (order is not important)?. This problem should have a large number of solutions, since 8 isn't the maximum number of bishops you can put on the board. The max is 13 or 14, i think. I haven't worked a solution out completely, but maybe post your solution and we'll evaluate the logic? I calculated that there are 15 possible places to place 8 or any other number of bishops, just as Mad Twit posted above: Follow the chessboard from corner to corner and their are 14 diagonals which the bishops can go in. The first diagonal only has one square so only one space for a bishop The second diagonal only has two squares so two places for a bishop The third diagonal has 3 squares but one is diagonal to the first bishop so again only two spaces for a bishop The fourth diagonal has 4 squares and one of them is diagonal to the second bishop The fifth diagonal has 5 squares and two of them are diagonal to the third and first bishops Carry on going along the diagonals and you get the sum below 1*2*2*3*3*4*4*5*3*3*2*2*1=103680 Rotate the chessboard around by 45 degrees and treat it the same as the Rooks Then I got C(158) because we have this number of combinations of 8 places out of 15 places. Then multiplied those and found 5,337,446,400. I assumed each place is named as a1,a2,..b1,b2 as in chess. So didn't need to exclude symmetrics. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 6, 2009 Report Share Posted June 6, 2009 Very close. I have a ballpark estimate, and it's pretty close to yours. How did you do that? Now I'm getting 135,137,760. still in your ballpark? Spoiler for this is how I got the number..: You can put a total of 14 Bishops on an 8x8 board so they can't attack one another. There are 22,522,960 scenarios of doing that. I think for every scenario of that happening, you can have 6 times as many for only 8 Bishops.(more less a geuss)But if thats the case, then take the 22,522,960*6=135,137,760 Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 6, 2009 Report Share Posted June 6, 2009 (edited) Dang... I'm onto a solution... but had a bug in my code. No time to rerun. I'll repost a solution in a couple of minutes. Edited June 6, 2009 by Phatfingers Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 6, 2009 Report Share Posted June 6, 2009 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 Quote Link to comment Share on other sites More sharing options...
0 Guest Posted June 6, 2009 Report Share Posted June 6, 2009 (edited) 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 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. Edited June 6, 2009 by James8421 Quote Link to comment Share on other sites More sharing options...
Question
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 by bushindoLink to comment
Share on other sites
31 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.