Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I keep reading about a proposed method of finding solutions to the $n$-queens problem using determinants, but I can't find any specific details anywhere. Can somebody explain to me how to find solutions to $n$-queens using determinants or point me in the right direction?

share|improve this question
2  
I'm guessing it all started with this paper... –  J. M. Sep 24 '11 at 18:26
    
See this survey paper as well. –  J. M. Sep 24 '11 at 18:32

1 Answer 1

It's in Glaisher's paper mentioned in the first comment by J.M., but I'll give it here for those who can't access the paper. We'll do the example in the $8 \times 8$ case, and it should be clear how to generalize it to $n \times n$.

Construct the following matrix, noting how the pattern of letters and numbers go.
$$A = \begin{bmatrix} a_1 & c_2 & e_3 & g_4 & i_5 & k_6 & m_7 & o_8 \\ b_2 & a_3 & c_4 & e_5 & g_6 & i_7 & k_8 & m_9\\ d_3 & b_4 & a_5 & c_6 & e_7 & g_8 & i_9 & k_{10}\\ f_4 & d_5 & b_6 & a_7 & c_8 & e_9 & g_{10} & i_{11}\\ h_5 & f_6 & d_7 & b_8 & a_9 & c_{10} & e_{11} & g_{12}\\ j_6 & h_7 & f_8 & d_9 & b_{10} & a_{11} & c_{12} & e_{13}\\ l_7 & j_8 & h_9 & f_{10} & d_{11} & b_{12} & a_{13} & c_{14}\\ n_8 & l_9 & j_{10} & h_{11} & f_{12} & d_{13} & b_{14} & a_{15}\\ \end{bmatrix}$$

If you construct $\det(A)$, and you strike out all terms in which the same letter or number appear more than once, then the terms that remain give exactly the solutions to the 8 queens problem.

So, why is this? Well, each term in $\det(A)$ has exactly one element from each row and each column, so using the determinant inherently eliminates board positions in which you have more than one queen in a row or column. Striking out all terms that have the same letter or number removes the board positions in which you have more than one queen in the same diagonal. What remains must be placements of 8 queens in which none are in the same row, column, or diagonal. (There's probably a better way to set up the matrix above, but this is how Glaisher does it. Also, there are going to be $n!$ terms in the determinant, making that computationally nasty, but Glaisher gives some ways to simplify the process.)

If you use the permanent rather than the determinant, strike out terms as above, and let all variables be 1, then you would have the number of solutions to the $n$ queens problem.

Added: I found a Google Books link to Glaisher's paper mentioned above and in J.M.'s first comment.

share|improve this answer
    
Thanks! I know about Glaisher's paper (which is why I posted that comment), but I have no access to it so I couldn't answer. His solution looks very clever... –  J. M. Sep 25 '11 at 5:02
    
@J.M.: I added a link to Glaisher's paper via Google books. –  Mike Spivey Sep 25 '11 at 5:13
    
Just thinking out loud here. Consider the matrix $A\in M_{n\times n}(\Lambda(V)\otimes\Lambda(V))$, with $\mathrm{dim}\;V=2n-1$, defined by $\alpha_{ij}=e_{i+j-1}\otimes e_{n+i-j}$: every two components that live on the same diagonal will share either the first or second part of the tensor product. If we compute $\det A$ (with $\wedge$ as multiplication), nonsolutions will clearly die off, but would it then list out all true solutions to the $n$-queens puzzle, or would the alternating sign of the wedge product allow for some of the solutions to kill themselves? (cont'd) –  anon Sep 25 '11 at 22:11
    
I worked out $n=4$ and it appears the two solutions (which are mirror images of each other) do not annihilate each other, but I can't tell if that applies more generally. It would be very interesting if this concept worked out. –  anon Sep 25 '11 at 22:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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