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

It has been known since the 1850's (or even much earlier) that 5 queens could be placed on an 8*8 chessboard so that every square on the board lies in the same row, column, or diagonal as at least one of the queens. It was also "known" that this could not be done with 4 queens. But I have not been able to obtain or track down any rigorous mathematical proof of this that could be (or could have been) carried out in a reasonable time by a human being with pencil and paper. There are altogether 635376 ways of placing 4 queens on an 8*8 chessboard. Does anyone know of a combinatorial algorithm, exploiting the symmetries of the chessboard, which would reduce the number of cases to be considered to the hundreds (or, at most, the low thousands.)? This is, of course, a trivial problem for modern computers, which have many times since verified that 5 queens are needed.

share|improve this question
    
I'll start with the obvious trivial observation that doesn't get close at all. The symmetry group of the square has 8 elements. Supposing that a typical configuration of 4 queens has none of those symmetries, you reduce the number of configurations by about a factor of 8, so there are "only" roughly $10^6$ to consider. –  Mark Meckes Jul 2 '10 at 18:42
    
You might consider the subproblem of placing four queens on a chess board so that all the white squares are covered. You may be able to argue that this is not possible unless at least three of the queens sit on white squares. But now there are the black squares to worry about... . Gerhard "Ask Me About System Design" Paseman, 2010.07.02 –  Gerhard Paseman Jul 2 '10 at 19:21
    
Well... you need at least 3 since each queen can cover up to 32 squares. And they cover at least one common square. –  john mangual Jul 2 '10 at 19:41
    
Unfortunately, the above argument does not hold: You can place four queens so that all the squares of one color are covered. However, you may be able to us this to show that any covering must have two queens on each color square, and then use that to limit the possibilities for covering the white squares. Gerhard "Ask Me About System Design" Paseman, 2010.07.02 –  Gerhard Paseman Jul 2 '10 at 19:42
3  
I wonder if the following naive approach might lead to a manageable number of cases: After placing a single queen somewhere, there are at least two uncovered 3x3 triangles left. You can cover them completely by placing queens in them, but if you do that for both, the remaining uncovered squares cannot be covered by a single queen. If you do it for one, the squares in the other triangle that are still not covered place some rather strong restrictions on the remaining two queens. Finally, if you place the second queen outside the two triangles, there are uncovered squares in both... –  Sebastian Reichelt Jul 2 '10 at 20:46
add comment

3 Answers 3

The problem of finding the minimum number of queens needed to cover an n-by-n board is the queens domination problem. According to http://ajc.maths.uq.edu.au/pdf/15/ocr-ajc-v15-p145.pdf , "Although there is currently no mathematical proof that these values [the known minimum numbers of queens] are correct, they have been verified by computer."

According to http://www.combinatorics.org/Volume_8/PDF/v8i1r29.pdf , "...current knowledge that [among other things, the queens domination number for an 8-by-8 board is greater than 4], comes from exhaustive search."

share|improve this answer
20  
That's a little strange: a computer calculation doesn't count as a mathematical proof? –  Pete L. Clark Jul 2 '10 at 22:24
1  
The calculation by itself, no. The calculation can support, contribute to, or be a major part of a proof. I think that some words are needed to make the link between the calculation and what the calculation supports, and the combination of words and calculation can then form a mathematical proof. Gerhard "Ask Me About System Design" Paseman, 2010.07.02 –  Gerhard Paseman Jul 2 '10 at 23:25
13  
@Pete: perhaps the authors intend that a mathematical proof is one which, while may not deserve a place in The Book, has a place in A Scroll, or perhaps on A Few Sheets of Papyrus. :) –  Willie Wong Jul 2 '10 at 23:44
1  
More citations: minimum dominating set of queens: A trivial programming exercise? portal.acm.org/citation.cfm?id=1715994 Also: dx.doi.org/10.1016/S0012-365X(02)00802-6 –  Junkie Jul 3 '10 at 0:24
1  
Related sequences: oeis.org/classic/A075458 and oeis.org/classic/A075324 –  Max Alekseyev Jul 3 '10 at 1:49
show 2 more comments

The number of fundamental arrangements one needs to check to prove there is no solution with 4 queens is about $\frac{1}{8}{64 \choose 4}\sim 10^5$ as Mark Meckes noted in his comment.

This number can be greatly reduced if we choose to inspect the space of solutions with $5$ queens. Clearly, every hypothetical $4$ queens' solution generates a family of $5$ queens' solutions (just place the $5$th queen at any of the $60$ remaining free squares).

Now, there are only $638$ fundamental arrangements with $5$ queens. All $4860$ solutions can be obtained from the fundamental arrangements by rotation and reflection. This was reportedly first calculated `by hand' by A.M. Yaglom and I.M. Yaglom (check out "Across the Board: The Mathematics of Chessboard Problems" by John J. Watkins). It seems to be a pretty feasible task to check that one cannot remove a queen in any of those arrangements and still get a dominating arrangement.

share|improve this answer
2  
Some of the suggestions for reducing the number of cases to be considered are very interesting, especially the one based on the 638 fundamental solutions using 5 queens. But would this not also require a proof that no arrangement of 5 queens (other than those obtained by rotations and reflections from the 638 fundamental solutions) could cover every square on the board. –  Garabed Gulbenkian Jul 13 '10 at 20:09
1  
Yes, several authors mention that the proof is due to Yaglom and Yaglom but I haven't managed to find the exact reference to a published version of the proof. –  Andrey Rekalo Jul 23 '10 at 14:21
2  
Paul Burchett in his 2005 Master's thesis (citeseerx.ist.psu.edu/viewdoc/…) cites A.M. Yaglom, I.M. Yaglom, Challenging mathematical problems with elementary solutions. Volume 1: Combinatorial Analysis and Probability Theory 1964. A Dover reprint of Yaglom and Yaglom is available through Amazon.com –  Doug Chatham Jul 23 '10 at 15:34
1  
@rdchat: Thank you for the comment. Actually, I've looked into the book and I did not find the result there! –  Andrey Rekalo Jul 23 '10 at 15:52
9  
Somewhat remarkably 5 queens suffice to cover a 11x11 board! Not sure when this was first observed or by whom. –  Noam D. Elkies May 27 '11 at 0:55
show 6 more comments

I also wonder whether the formation came before or after 1990, because that is when Spencer came up with the lower bound for n=11. I know first-hand that formations can be searched for by hand for say, up to n=20 with reasonable results (note that is much different than actual proof that the formation is minimal, for if we find the formation we've only found an upper bound). So it's quite possible that someone found the formation first, and then Spencer might have been the first to observe it. Of course it's also possible that Spencer's bound came first.

I found Dr Chatham's comment interesting enough to vote it up, although seeing as how I'm stuck at one reputation, I can't.

share|improve this answer
2  
Now you should be able to vote, I guess. –  Stefan Kohl Nov 4 '13 at 11:16
add comment

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.