Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
I get 4860 of them. I'll check to see if any obviously aren't adjacent to any others. –  Eric Tressler Aug 25 '10 at 21:19
    
I just posted all of the solutions at math.ucsd.edu/~etressle/queens.txt. I was going to give you a list of coordinates, too, but I just typed ./a.out > main.cpp by accident, and so those are not going to be forthcoming. –  Eric Tressler Aug 25 '10 at 21:25
    
Note that I am not the original asker, I was just helping him out. With coordinates it would be trivial to perform BFS, but alas... –  Eric Tressler Aug 25 '10 at 21:33
    
It's still not difficult, but I don't have time to parse that file right now and do it. I'll do it tonight if someone else hasn't. –  Eric Tressler Aug 25 '10 at 21:38
6  
You are a generous dude. –  Will Jagy Aug 25 '10 at 21:40
add comment

1 Answer 1

up vote 11 down vote accepted

Revised and correct:

589 equivalence classes.

http://www.math.ucsd.edu/~etressle/classes.txt

It seems that the pairs (#vertices,#components) are (1,388) (2,100) (3,40) (4,34) (5,20) (18,4) (20,2) (3804,1) – damiano 15 hours ago

1: Class I.D. 2, 4, 5, 6, 7,..., 589.
2: Class I.D. 22, 29, 35, 47, 48,..., 579.
3: Class I.D. 28, 33, 38, 49, 58,..., 574.
4: Class I.D. 13, 90, 95, 126, 141,..., 576. 
5: Class I.D. 32, 37, 62, 89, 97,..., 395. 
18: Class I.D. 17, 31, 185, 303.
20: Class I.D. 3, 75.
3804: Class I.D. 1.
share|improve this answer
    
Thanks, Eric!$$ –  David Steinberg Aug 26 '10 at 0:24
1  
(I thought I was being clever by adding dollar signs to fill-up the 15 character minimum, but I forgot that you can't use latex in comments. Ho hum.) –  David Steinberg Aug 26 '10 at 0:26
    
I am not sure that I understand what the file means: is there a huge component and lots of tiny components? –  damiano Aug 26 '10 at 0:32
1  
You can use LaTeX... $i = \sqrt{-1}$ –  Andrea Ferretti Aug 26 '10 at 0:36
    
So in particular, CLASS 9: (0,0) (1,1) (3,5) (5,3) (7,7) turns out to be one of many isolated solutions –  Aaron Meyerowitz Aug 26 '10 at 0:41
show 2 more comments

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.