Puzzle
11 minute read

Ponder This Challenge - August 2008 - Variation on the 8-queen problem

Ponder This Challenge:

This month's puzzle is a variant of the famous 8-queens problem (see http://en.wikipedia.org/wiki/Eight_queens).

The original problem is to place as many queens as possible on an 8x8 chess board such that no queen will threaten another (a queen threatens all the squares in its row, column, and both diagonals).

In our version we need to place as many queens as possible on an NxN board, such that each queen will threaten at most *one* other queen. We ask to prove an upper bound and give a solution matching it for the standard 8x8 board as well as for a 30x30 board. The solution should be sent as pairs of x,y coordinates.

Thanks to Vladimir Sedach for suggesting the question.

UPDATE 8/11/08: As some of you wrote to us, it seems that our problem above is ill defined since we did not say if a queen A can block queen B from threatening queen C; However, it is easy to see that it does not matter in our case since queen A threatens more than one queen (both queens B and C) which is not allowed.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

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

Solution

  • 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

Solvers

  • Frank Yang (08.05.2008 @05:06 PM EDT)
  • Hongcheng Zhu (08.06.2008 @08:07 AM EDT)
  • Eugene Vasilchenko (08.06.2008 @11:57 AM EDT)
  • Balakrishnan V (08.06.2008 @08:54 PM EDT)
  • John Tromp (08.07.2008 @11:45 AM EDT)
  • Andreas Eisele (08.09.2008 @07:23 AM EDT)
  • Joe DeVincentis (08.09.2008 @11:13 AM EDT)
  • Steffen Wolf (08.11.2008 @05:25 AM EDT)
  • Harald Bögeholz + Andreas Stiller (08/12/2008 02:45 PM EDT)
  • Nyles Heise (08/13/2008 12:33 AM EDT)
  • John G Fletcher (08/14/2008 12:38 AM EDT)
  • Danny Antonetti (08/14/2008 12:58 AM EDT)
  • Máté Bartalos (08/15/2008 08:17 AM EDT)
  • Li Zou (08/15/2008 12:53 AM EDT)
  • Michael Brand (08/15/2008 04:55 PM EDT)
  • Gary M. Gerken (08/20/2008 09:57 AM EDT)
  • Josh Bowman (08/21/2008 12:15 PM EDT)
  • Bojan Basic (08/21/2008 11:16 AM EDT)
  • Dan Dima (08/22/2008 12:03 PM EDT)
  • David Papp (08/24/2008 10:39 PM EDT)
  • Zhou Guang (08/24/2008 11:24 PM EDT)
  • Michael Schaaf (08/25/2008 02:22 PM EDT)
  • Albert Stadler (08/27/2008 01:54 PM EDT)
  • Matt Gara (08/28/2008 01:42 AM EDT)
  • Raphael Finkel (08/28/2008 09:39 AM EDT)
  • Nagy Zoltan (08/30/2008 05:53 PM EDT)
  • Jesse Kolman (09/01/2008 02:30 PM EDT)

Related posts