## Is there a good argument for why you can’t place 4 queens which cover a chessboard?

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.

-
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 2010 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 2010 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 2010 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 2010 at 19:42
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 2010 at 20:46

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."

-
That's a little strange: a computer calculation doesn't count as a mathematical proof? – Pete L. Clark Jul 2 2010 at 22:24
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 2010 at 23:25
@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 2010 at 23:44
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 2010 at 0:24
Related sequences: oeis.org/classic/A075458 and oeis.org/classic/A075324 – Max Alekseyev 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.

-
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 2010 at 20:09
I am a little puzzled by the estimate of Mark Meckes for the number of cases that need to be considered. It is stated to be about !0^6 or even more. But I must be reading it incorrectly, since the number of subsets of 4 elements contained in a set of 64 elements is only 635376. – Garabed Gulbenkian Jul 13 2010 at 20:29
@Garabed: That is roughly $10^{6}$... – BlueRaja Jul 14 2010 at 22:18
That was a typo in my comment. I meant $635376/8 \approx 10^5$. – Mark Meckes Jul 23 2010 at 14:03
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 2010 at 15:34