Ponder This Challenge - February 2023 - The queens and kings problem

In the eight queens problem, eight queens must be placed on a chessboard in such a way that no pair of queens is currently threatening one another. One possible solution to the eight queens problem is this:

In any solution to the eight queens problem, all the empty squares on the chessboard are threatened by at least two queens. We refer to a square that is threatened by exactly two queens as safe. These squares are marked here in green:

For the given configuration of queens, there is only one way to put four kings on the safe squares such that no two kings are currently threatening one another:

With apologies to standard chess notation, we can describe the locations of the queens and kings on this board using the following two lists of coordinates:
[(0, 2), (1, 5), (2, 3), (3, 1), (4, 7), (5, 4), (6, 6), (7, 0)]
[(1, 7), (3, 0), (7, 1), (7, 3)]

For $n=14$, an $n\times n$ board and the following queen configuration:
[(0, 1), (1, 9), (2, 7), (3, 5), (4, 3), (5, 12), (6, 10), (7, 13), (8, 11), (9, 6), (10, 4), (11, 2), (12, 0), (13, 8)]

Is it possible to find arrangement of $n$ kings. One such arrangement is
[(0, 0), (1, 10), (2, 0), (4, 0), (4, 2), (9, 2), (9, 9), (11, 0), (11, 7), (11, 11), (13, 5), (13, 9), (13, 11), (13, 13)]

There are 41 possible arrangements of $n$ kings in total.

Your goal: Find a placement of $n=20$ queens on an $n\times n$ board such that no pair of queens threatens each other, and the number of different ways to place $n$ kings on the safe squares without any pair of kings currently threatening one another is 48.

Supply your answer in a list of the queen positions, as in the above example.

A bonus "*" will be given for finding a placement of $n$ queens on an $n\times n$ board such that no pair of queens is currently threatening one another, and there is no way to place $n$ kings on the safe squares without any pair of kings threatening each other, for $n\ge 26$.

Solution

• Click here to view the solution

  February 2023 Solution:

  There are many possible solutions; these specific ones were found by Motty Porat:
  N=20:
  [(0, 0), (1, 2), (2, 4), (3, 1), (4, 9), (5, 12), (6, 18), (7, 15), (8, 19), (9, 5), (10, 16), (11, 10), (12, 3), (13, 17), (14, 6), (15, 8), (16, 13), (17, 11), (18, 7), (19, 14)]

  N=31:
  [(0, 0), (1, 2), (2, 4), (3, 1), (4, 3), (5, 8), (6, 10), (7, 12), (8, 14), (9, 16), (10, 18), (11, 21), (12, 25), (13, 28), (14, 26), (15, 24), (16, 30), (17, 6), (18, 29), (19, 5), (20, 11), (21, 9), (22, 7), (23, 13), (24, 20), (25, 17), (26, 19), (27, 22), (28, 15), (29, 23), (30, 27)]

Solvers

• *Lorenz Reichel (2/2/2023 3:06 PM IDT)
• *Paul Revenant (2/2/2023 4:54 PM IDT)
• *Amos Guler (3/2/2023 3:10 AM IDT)
• *Bertram Felgenhauer (3/2/2023 6:03 AM IDT)
• *Gary M. Gerken (3/2/2023 7:12 AM IDT)
• *Alper Halbutogullari (3/2/2023 8:46 AM IDT)
• *Reiner Martin (3/2/2023 1:59 PM IDT)
• *Lorenzo Gianferrari Pini (3/2/2023 4:33 PM IDT)
• Vamsi Krishna Talupula (3/2/2023 7:28 PM IDT)
• Giorgos Kalogeropoulos (3/2/2023 8:29 PM IDT)
• *Daniel Bitin (3/2/2023 11:34 PM IDT)
• *Dieter Beckerle (4/2/2023 3:45 PM IDT)
• *Daniel Chong Jyh Tar (4/2/2023 5:24 PM IDT)
• Richard Gosiorovsky (4/2/2023 6:09 PM IDT)
• *Todd Will (4/2/2023 6:47 PM IDT)
• David Greer (4/2/2023 8:27 PM IDT)
• V.Barbera (5/2/2023 1:08 AM IDT)
• *Stefan Berger (5/2/2023 3:42 PM IDT)
• *Hakan Summakoğlu (5/2/2023 7:59 PM IDT)
• *Tim Walters (6/2/2023 2:09 AM IDT)
• *David F.H. Dunkley (6/2/2023 2:42 AM IDT)
• *Harald Bögeholz (6/2/2023 10:27 AM IDT)
• Graham Hemsley (6/2/2023 11:22 AM IDT)
• Dan Dima (6/2/2023 2:54 PM IDT)
• *Guillaume Escamocher (6/2/2023 5:08 PM IDT)
• *Latchezar Christov (7/2/2023 6:32 PM IDT)
• *Bert Dobbelaere (7/2/2023 9:11 PM IDT)
• *Vladimir Volevich (8/2/2023 2:33 PM IDT)
• *K S (8/2/2023 11:23 PM IDT)
• *Martin Thorne (9/2/2023 7:30 PM IDT)
• *Andreas Knüpfer (9/2/2023 9:19 PM IDT)
• *Sanandan Swaminathan (11/2/2023 11:24 AM IDT)
• Alex Fleischer (11/2/2023 3:01 PM IDT)
• *John Tromp (12/2/2023 12:56 AM IDT)
• Clive Tong (13/2/2023 10:32 AM IDT)
• *Thomas Ilsche (13/2/2023 4:56 PM IDT)
• *Stéphane Higueret (13/2/2023 10:55 PM IDT)
• *Chris Shannon (14/2/2023 8:34 PM IDT)
• *Phil Proudman (15/2/2023 5:10 PM IDT)
• Sri Mallikarjun (15/2/2023 7:28 PM IDT)
• *Mario Bielert (15/2/2023 9:38 PM IDT)
• *Marco Bellocchi (16/2/2023 12:02 AM IDT)
• Michael Liepelt (17/2/2023 8:20 AM IDT)
• Ranjit Eswaran (18/2/2023 4:12 PM IDT)
• *Phong Kah Ho (18/2/2023 9:09 PM IDT)
• Prashant Wankhede (20/2/2023 3:36 AM IDT)
• *Jean-Matthieu Schertzer (20/2/2023 12:47 PM IDT)
• Jesús V (20/2/2023 8:25 PM IDT)
• *Li Li (21/2/2023 7:28 PM IDT)
• *Evert van Dijken (22/2/2023 12:58 PM IDT)
• *Alexander Marschoun (23/2/2023 10:23 PM IDT)
• *Nyles Heise (25/2/2023 6:12 AM IDT)
• *Andreas Puccio (27/2/2023 12:42 PM IDT)
• *Motty Porat (28/2/2023 7:33 PM IDT)
• Jet Semrick (1/3/2023 12:53 AM IDT)
• *Radu-Alexandru Todor (1/3/2023 1:09 AM IDT)
• *Stephen Herbert Jr (1/3/2023 9:05 PM IDT)
• John Goh (4/3/2023 5:15 PM IDT)
• Virginia Ardévol Martínez (5/3/2023 11:14 PM IDT)
• Elias Werner (13/3/2023 6:32 PM IDT)