"Pintando" el tablero es una buena opción, con un árbol de búsqueda, si llega a un punto muerto retrocede a un esta anterior y así en forma recursiva.
Una solución es , con Matriz de bits 8x8, 1=Reina, 0=Casilla vacía :
$40,$10, $4, $1,$20,$80, $2 , $8
(Noten la simetría del resultado, que no es casualidad)
