Hosted by The Math Forum

Problem of the Week 1178

Unaligned Queens

_____________________________________________
MacPoW Home ||  Forum PoWs ||  Teachers' Place ||  Student Center ||  Search MacPoW
_____________________________________________

Place queens on a 7 × 7 chessboard so that no three of them lie on a horizontal, vertical, or (45-degree) diagonal line, but so that the addition of a queen to any open square violates this condition. The idea is to do this with as few queens as possible.

For example, on a 3 × 3 board, the minimal solution uses four queens: Place them at four corners (or use a 2 × 2 block).

There are many variations. I will discuss them in more detail in the solution post.

  1. The Martin Gardner Problem: Replace 7 by general n in the problem above. This is an unsolved problem in general.
  2. Dudeney's No-Three-In-Line Problem (1917): What is the largest number of markers that can be placed on an n × n board so that there are no three in a line, where a "line" is a general line in the plane? This is a difficult problem, with answer known only up to n = 46. Note that 2n is an obvious maximum since 2n + 1 markers would include three in a vertical line.

Thanks to Ed Pegg, Joseph DeVincentis, and Mark Rickert.

Source: Cooper, Pikhurko, Schmitt, Warrington, Martin Gardner's minimum No-3-in-a-line problem, Amer Math Monthly, 121, March 2014, 213-221.

© Copyright 2014 Stan Wagon. Reproduced with permission.

[View the solution]

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.


1 April 2014