Problem of the Week 1178

Unaligned Queens

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]