MHB What is the Maximum Number of Equivalence Classes for the Eight Queens Problem?

  • Thread starter Thread starter Ackbach
  • Start date Start date
  • Tags Tags
    2015
Ackbach
Gold Member
MHB
Messages
4,148
Reaction score
93
Here is this week's POTW:

-----

The statement of the Eight Queens Problem is to place eight queens on a regular chessboard so that no two queens are attacking each other. For anyone ignorant of the rules of chess, queens attack in any direction vertically or horizontally or in either $45^{\circ}$ diagonal. (We will ignore the $n$-Queen problem on an $n\times n$ chessboard.) If you examine the wikipedia page portion on the Solutions, it claims that there are 12 fundamental solutions to the problem. These fundamental solutions form other solutions by rotations and reflections only. Suppose we allow translations as well, so that two solutions are considered the "same" (in the same equivalence class), if one solution can be obtained from the other by a combination of translations, rotations, and reflections. Moreover, we will allow solutions to "wrap-around" the edges of the board. Provide an upper bound, smaller than $12$, on the number of such equivalence classes.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!
 
Physics news on Phys.org
Honorable mention goes to Opalg, with an upper bound of 11. Here is my solution:

I claim the upper bound is no more than 6. Solutions 1, 2, 3, 4, 6, 8, 10 are all obtained from the following by rotations, reflections, or translations:

View attachment 4463

Notice this is a bigger chessboard than usual - it's to illustrate the pattern before it wraps around. Also notice that this isn't technically a solution, as there are two queens attacking each other. Wrap-around solves this issue: where this pattern is the basis of the solution, the pattern wraps around in such a way that the problem resolves.

I have not yet seen any definite pattern in the remaining solutions: 5, 7, 9, 11, and 12. If anyone else sees a pattern there, I'd be thrilled to know about it. It's certainly not clear that any of these solutions can be obtained from the above.
 

Attachments

  • Chessboard for Eight Queens Problem - Copy.gif
    Chessboard for Eight Queens Problem - Copy.gif
    11 KB · Views: 135

Similar threads

Back
Top