About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
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 xi the number of rows with i queens and by yi the number of columns with i queens.
Clearly, x0+x1+x2 = n and hence x1+x2 ≤ n. Same is true for y: y1+y2 ≤ n.
Each of the 2x2 queens in the x2 rows already threatens a queen, so at least 2x2 columns has only one queen, i.e. 2x2 ≤ y1.
Similarly 2y2 ≤ x1.
The number of queens m is x1+2x2 and also m = y1+2y2.
Simple algebra shows that:
m = (x1+2x2 + y1+2y2)/2 ≤ (x1+4/3x2+1/3y1 + y1+4/3y2+1/3x1)/2 = 2(x1+x2 +y1+y2)/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