A configuration of queens on an 8 by 8 chessboard (or n by n if you like) is a queen domination if every square on the board lies in the same row, column, or diagonal as at least one of the queens. The Queens Domination Problem is to find the minimum number of queens necessary for a queen domination. A solution to the Queens Domination Problem is a queen domination using the minimum number of queens.
For the 8 by 8 chessboard, brute force has shown that 5 queens is the minimum number. More discussion about that here.
The adjacency relation on the set of solutions to the Queens Domination Problem is defined as follows: we say solutions are adjacent if they differ by only the placement of one queen. For example: C3, E4, D5, B6, F4 is adjacent to C3, E4, D5, B6, F2.
How many equivalance classes are there in the equivalance relation generated by adjacency?
In other words, starting with one solution, can we reach any other solution by moving one queen at a time, such that the result of each move is itself a solution?