Solving $n$-queens with determinants

Question

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?

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.