2
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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}$. It's the same result either way. $\endgroup$ – Varun Vejalla Sep 24 at 23:36
  • 1
    $\begingroup$ In b. and c. you need to multiply the numbers instead of adding them. Also, don't forget to divide by $8!$ as you did in a. Then you'll get the correct answers. $\endgroup$ – Klaus Sep 24 at 23:44
  • 1
    $\begingroup$ Just curious, are you in an AI class or something like that? I ask because we had a similar assignment in my class. $\endgroup$ – Varun Vejalla Sep 24 at 23:48
  • $\begingroup$ @VarunVejalla It's for a computer science class about design and analysis of algorithms. We were just working on a unit in brute-force algorithms. $\endgroup$ – maths Sep 24 at 23:56
3
$\begingroup$

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!$.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

If no two queens are in the same row, then there is exactly one queen in each row. There are $8$ possible locations for a queen in each row, so there are $8^8=16\,777\,216$ possible positions with no two queens in the same row. Similarly, in (c) you should also be multiplying: there are $8$ possible columns for the queen in the first row, after which there are $7$ possible columns for the queen in the second row, and so on, so there are $8!=40\,320$ possible positions with no two queens in the same row or column.

Yes, dividing each of these figures by $10^{10}$ will tell you how long the computation itself would take.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.