11
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ I get 4860 of them. I'll check to see if any obviously aren't adjacent to any others. $\endgroup$
    – Eric Tressler
    Aug 25, 2010 at 21:19
  • $\begingroup$ 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. $\endgroup$
    – Eric Tressler
    Aug 25, 2010 at 21:25
  • $\begingroup$ 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... $\endgroup$
    – Eric Tressler
    Aug 25, 2010 at 21:33
  • $\begingroup$ 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. $\endgroup$
    – Eric Tressler
    Aug 25, 2010 at 21:38
  • 6
    $\begingroup$ You are a generous dude. $\endgroup$
    – Will Jagy
    Aug 25, 2010 at 21:40

1 Answer 1

Reset to default
11
$\begingroup$

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.
Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ (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.) $\endgroup$
    – David Steinberg
    Aug 26, 2010 at 0:26
  • $\begingroup$ I am not sure that I understand what the file means: is there a huge component and lots of tiny components? $\endgroup$
    – damiano
    Aug 26, 2010 at 0:32
  • 1
    $\begingroup$ You can use LaTeX... $i = \sqrt{-1}$ $\endgroup$
    – Andrea Ferretti
    Aug 26, 2010 at 0:36
  • $\begingroup$ So in particular, CLASS 9: (0,0) (1,1) (3,5) (5,3) (7,7) turns out to be one of many isolated solutions $\endgroup$
    – Aaron Meyerowitz
    Aug 26, 2010 at 0:41
  • $\begingroup$ It seems that the pairs (#vertices,#components) are (1,388) (2,100) (3,40) (4,34) (5,20) (18,4) (20,2) (3804,1) $\endgroup$
    – damiano
    Aug 26, 2010 at 1:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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