Ponder This

August 2008

<<July August September>>

First we prove an upper bound of 4N/3 for the NxN board.

Since no queen threatens more than one other queen, there are at most two queens per row (column).

Denote by x_i the number of rows with i queens and by y_i the number of columns with i queens.

Clearly, x₀+x₁+x₂ = n and hence x₁+x₂ ≤ n. Same is true for y: y₁+y₂ ≤ n.

Each of the 2x₂ queens in the x₂ rows already threatens a queen, so at least 2x₂ columns has only one queen, i.e. 2x₂ ≤ y₁.

Similarly 2y₂ ≤ x₁.

The number of queens m is x₁+2x₂ and also m = y₁+2y₂.

Simple algebra shows that:
m = (x₁+2x₂ + y₁+2y₂)/2 ≤ (x₁+4/3x₂+1/3y₁ + y₁+4/3y₂+1/3x₁)/2 = 2(x₁+x₂ +y₁+y₂)/3 ≤ 4/3 n.

The upper bound for 8x8 board is 10 and a possible solution achieving it is:

*	-	-	-	-	-	-	-
-	-	-	-	*	*	-	-
-	*	-	-	-	-	-	-
-	*	-	-	-	-	-	-
-	-	-	-	-	-	*	-
-	-	-	-	-	-	*	-
-	-	*	*	-	-	-	-
*	-	-	-	-	-	-	-

Which is (1,1) (2,5) (2,6) (3,2) (4,2) (5,7) (6,7) (7,3) (7,4) (8,1).
A possible solution for a 30x30 board is:
( 1, 3) ( 2,16) ( 2,20) ( 3, 6) ( 4,12) ( 4,30) ( 5, 9) ( 5,18) ( 6,26) ( 7, 8) ( 7,17) ( 8,27) ( 9, 3) (10,27) (11, 6) (12,21) (12,24) (13,29) (14,29) (15,26) (16, 5) (17, 2) (18, 2) (19, 7) (19,10) (20,25) (21, 4) (22,28) (23, 4) (24,14) (24,23) (25, 5) (26,13) (26,22) (27, 1) (27,19) (28,25) (29,11) (29,15) (30,28)

Thanks for IBM Haifa's CSP (Constrain Satisfaction Problem) solver team for the help in solving this puzzle.

---

Some of you, our devoted ponder-this solvers, gave us the following elegant solution which can be generelized to any 6Nx6N board. It is the cartesian product of an original (no queens threatens any other) 5-queen solution with our (a queen can threaten at most one other) 6-queens solution:

-

-

-

-

-

*

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

*

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

*

-

-

-

-

*

-

-

-

-

-

-

-

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com