Eight-queens problem Consider the classic puzzle of placing eight queens on an 8 × 8 chessboard so that no two queens are in the same row or in the same column or on the same diagonal. How many ways are there so that a. no two queens are on the same square? b. no two queens are in the same row? c. no two queens are in the same row or in the same column?
Answers
a. Since we are working with an 8 x 8 chessboard, there are 64 possible positions to place a queen on. We can arrange items in 64 locations in 64! ways, but we must divide out by the number of blank spots, 56!, as well as the number of queens, 8!, since the queens are considered indistinguishable from each other. Hence, we arrive at 64!56!8!=4,426,165,368 positions.
b. The way I thought about part b. was to think about creating a "subset" of the problem. That is, each time we place a queen on the board, we know that we can no longer include that row in considering where to place the next queen; hence, we are considering a smaller problem size each time. We could place the first queen in any one of 64 ways, since we have 64 different squares; then, we remove the row in which we placed that queen from consideration when placing the second queen, so we will be working with a 7 x 8 chessboard with 56 positions in which to place a queen, etc. So, there are 64+56+48+40+32+24+16+8=288 positions so that no two queens are in the same row.
c. I used the same approach as in part b.: reducing the problem size so that once we place a queen, we remove that row and that column as legitimate locations for placing the next queen. So, for example, placing the first queen means that that row and that column are removed, so we consider placing the next queen in a 7 x 7 chessboard, etc. Using this approach, I obtained 64+49+26+25+16+9+4+1=204 possible positions.
please mark it as brainliest