Welcome to MathOverflow

Question

18

6

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.

edited Jul 2 2010 at 18:34

Noah Snyder
11.3k●1●26●70

asked Jul 2 2010 at 18:13

Garabed Gulbenkian
2,991●6●13

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

1

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

Doug Chatham · Answer 1 · 2010-07-02 21:30:08Z UTC

13

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

answered Jul 2 2010 at 21:30

Doug Chatham
473●4●8

10

That's a little strange: a computer calculation doesn't count as a mathematical proof? – Pete L. Clark Jul 2 2010 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 2010 at 23:25

7

@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

Andrey Rekalo · Answer 2 · 2010-07-23 14:23:58Z UTC

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.

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.