0
$\begingroup$

I am studying the $N$-Queens problem and have found the following statement

Now number of possible arrangements of $N$ Queens on $N \times N$ chessboard is $N!$, given you are skipping row or column, already having a queen placed. So average and worst case complexity of the solution is $O(N!)$ (since, you are checking all the possible solutions i.e. $N^N$ arrangements). The best case occurs if you find your solution before exploiting all possible arrangements. This depends on your implementation.

And if you need all the possible solutions, the best, average and worst-case complexity remains $O(N!)$

(Note: none of the other answers (or links on them) on the link above help in my understanding)

I don't understand this at all.

Surely the total number of possible arrangements (not the total number of solutions) for the $8$ Queens - assuming we have an 8x8 board (hence $N=8$) - will be

$64\cdot 63\cdot 62\cdot 61\cdot 60\cdot 59\cdot 58\cdot 57$

...based on what I learned from a similar problem (number of seating arrangements), which gives me a far, far greater value than $N^N$???

$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

The quote you have posted is making use of the fact that in the $N$-queens problem none of the queens is allowed to be threatening any of the others, so there must be exactly $1$ queen in each column (otherwise the queens in the same column would threaten each other). So if we want find solutions to the $N$-queens problem we need only consider potential solutions with $1$ queen per column. For each column choose a row in which to place a queen, giving us $N^N$ arrangements to check.

$\endgroup$
4
  • $\begingroup$ Ok, thanks. 1) Without this 1 Queen per column constraint, I would be correct with the number of combinations being 64*63*...57, right? 2) Can you please show how we can get $N^N$ by assuming there will only be one Queen per column? $\endgroup$
    – Wad
    Nov 30, 2019 at 19:48
  • 1
    $\begingroup$ @Wad to (1), yes, in general there are $\frac{(N^2)!}{(N^2 - N)!}$ ways to place $N$ markers on an $N\times N$ board with no restrictions. To (2) since we need to place $N$ queens there must be exactly one queen per column. In the first column choose one of $N$ squares to place a queen, similarly for each of the remaining $N - 1$ columns we have a choice of $N$ squares. So there are $N^N$ possible ways to do this. $\endgroup$
    – nbritten
    Nov 30, 2019 at 20:21
  • $\begingroup$ I'm sorry but I still don't understand how $N^N$ is obtained; this is not a strong point of mine. Could you (possibly diagrammatically) explain this deduction further, please? $\endgroup$
    – Wad
    Nov 30, 2019 at 21:27
  • 1
    $\begingroup$ Let's consider $n = 3$. We want to place 3 queens, one in each column. First place a queen in column a, there are 3 ways to do this. Next in column b, again 3 ways to do this, so $3\cdot 3 = 9$ total ways we could have placed our queens so far. Finally, choose one of the 3 positions in column c to place a queen. So all together there are $3^3 = 27$ ways we could have done this. This generalizes directly to $N$, we'll just place $N$ queens and have $N$ choices at each step, so $N^N$ possible ways to place them. $\endgroup$
    – nbritten
    Nov 30, 2019 at 21:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .