I am tasked with finding the answers to the following questions:
Part $1$: 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 different positions 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?
Once I have found the correct solutions to the three above questions, I am also asked to find the following:
Part $2$: Also estimate how long it would take to find all the solutions to the problem by exhaustive search based on each of these approaches on a computer capable of checking 10 billion positions per second.
So, what I need to solve here is not the Eight Queens Problem per se, but rather some intermediate steps toward finding the number of solutions to that problem. I would like some feedback on my reasoning and answers to these three questions. (Also, please note that I am required to determine the number of solutions by hand, not by using a computer program.) For part $1$:
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 $\frac{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.
For part $2$, would my solution simply be dividing my result in part a. by $10$ billion to obtain the estimated time?
Best Answer
For part a, you could also think about it as choosing the $8$ squares out of the $64$ available squares, so it would be $\binom{64}{8} = 4426165368$. It's the same result either way.
For part b, you should be multiplying to get $64\cdot56 \cdot48 \cdot 40 \cdot 32 \cdot 24 \cdot 16 \cdot 8$, but even this would be overcounting since there are duplicates. Specifically, dividing by the number of ways to order $8$ identical queens yields $\frac{64\cdot56 \cdot48 \cdot 40 \cdot 32 \cdot 24 \cdot 16 \cdot 8}{8!} = 8^8 = 16777216$. You could also think about this as the number of ways to arrange one queen in each row. There would be $8$ options for row $1$, $8$ for row $2$, etc.
Similarly, in c, you should be multiplying to find the number of different arrangements, and then dividing by $8!$ to get $8! = 40320$. You could also think about this as the number of ways to place one in each row, eliminating one option each time. There would be $8$ options for row $1$, $7$ options for row $2$, etc, to get $8!$.