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.
-
$\begingroup$ 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. $\endgroup$– Mark MeckesCommented Jul 2, 2010 at 18:42
-
$\begingroup$ 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 $\endgroup$– Gerhard PasemanCommented Jul 2, 2010 at 19:21
-
$\begingroup$ Well... you need at least 3 since each queen can cover up to 32 squares. And they cover at least one common square. $\endgroup$– john mangualCommented Jul 2, 2010 at 19:41
-
$\begingroup$ 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 $\endgroup$– Gerhard PasemanCommented Jul 2, 2010 at 19:42
-
6$\begingroup$ 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... $\endgroup$– Sebastian ReicheltCommented Jul 2, 2010 at 20:46
3 Answers
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."
-
29$\begingroup$ That's a little strange: a computer calculation doesn't count as a mathematical proof? $\endgroup$ Commented Jul 2, 2010 at 22:24
-
2$\begingroup$ 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 $\endgroup$ Commented Jul 2, 2010 at 23:25
-
19$\begingroup$ @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. :) $\endgroup$ Commented Jul 2, 2010 at 23:44
-
1$\begingroup$ 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 $\endgroup$– JunkieCommented Jul 3, 2010 at 0:24
-
2$\begingroup$ Related sequences: oeis.org/classic/A075458 and oeis.org/classic/A075324 $\endgroup$ Commented Jul 3, 2010 at 1:49
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.
-
3$\begingroup$ 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. $\endgroup$ Commented Jul 13, 2010 at 20:09
-
1$\begingroup$ 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. $\endgroup$ Commented Jul 23, 2010 at 14:21
-
2$\begingroup$ 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 $\endgroup$ Commented Jul 23, 2010 at 15:34
-
1$\begingroup$ @rdchat: Thank you for the comment. Actually, I've looked into the book and I did not find the result there! $\endgroup$ Commented Jul 23, 2010 at 15:52
-
11$\begingroup$ Somewhat remarkably 5 queens suffice to cover a 11x11 board! Not sure when this was first observed or by whom. $\endgroup$ Commented May 27, 2011 at 0:55
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.