Ponder This Challenge - May 2016 - Attacking chess pieces

Ponder This Challenge:

Find two different ways to place chess pieces on an 8x8 board so that each square is threatened exactly the same number of times.

Note that we are using single color pieces and you can use as many pieces as you want (not limited to the standard chess set); but each square can hold at most one piece.

Supply your answer as two sets of 64 characters (k for king, q for queen, r for rook, b for bishop, n for knight; p for pawn, and = for empty square).

For example, on a 4x4 board, placing 4 queens as follows:
= q q =
= = = =
= = = =
= q q =
gives the following threats numbers:
2 2 2 2
2 3 3 2
2 3 3 2
2 2 2 2
There is another way to get to the same numerical solution as well.

Note that a chess piece does *not* threaten the square it is occupying (otherwise the problem would be too simple).

Solution

• Click here to view the solution

  Using pawns makes it easier to solve the problem, even by manual trial and error. For example:

  ========	========
  n=====n=	===p====
  ========	========
  ========	===p====
  ========	p=====p=
  ========	========
  ========	========
  ========	========
  

  There is a nice solution using only bishops; here is an analytical way to find it. Define an attack 64x64 0-1 matrix A where a_{ij} is 1 if and only if a bishop placed on square i is threatening square j. We are looking for two binary vectors x_1 and x_2 such that A*x_1 = A*x_2. So we are looking for a vector d=x_1-x_2 whose values are from the set {-1,0,1} and A*d=0. Luckily, the kernel of matrix A over the rational number field contains such a vector, which gives us the solution:

  =b======	========
  b=======	========
  ========	========
  ========	========
  ========	========
  ========	========
  ========	=======b
  ========	======b=
  

  Extending matrix A to be 5*64x64 with the attacking patterns of all five types of chess pieces gives us a much larger kernel. However, it's not easy to find {-1,0,1} vectors in this linear space. As an example of a '**', we give Bert Dobbelaere's solution:

  =bkqqkb=	===rr===
  r=nnnn=r	q======q
  ========	kn====nk
  ========	bn====nb
  ========	bn====nb
  ========	kn====nk
  r=nnnn=r	q======q
  =bkqqkb=	===rr===
  

  See also Paolo Farinelli and David F.H. Dunkley's nice symmetric solution:

  =q======	=r======
  q==k=k==	r=======
  ==k===k=	===nnn==
  ========	===n=n==
  ==k===k=	===nnn==
  ===k=k==	========
  ========	=======b
  ========	======b=
  

Solvers

• *Robert Gerbicz (01/05/2016 05:57 PM IDT)
• **Bert Dobbelaere (01/05/2016 11:57 PM IDT)
• Jimmy Waters (02/05/2016 07:22 AM IDT)
• Kang Jin Cho (02/05/2016 07:28 PM IDT)
• *Rob Pratt (02/05/2016 08:12 PM IDT)
• Frank Schoeps (02/05/2016 10:46 PM IDT)
• **David F.H. Dunkley (02/05/2016 11:15 PM IDT)
• Alexander Ruff (03/05/2016 01:34 AM IDT)
• Benjamin Lui (03/05/2016 10:30 AM IDT)
• Tamir Ganor (03/05/2016 11:08 AM IDT)
• *János Csorba (03/05/2016 12:57 PM IDT)
• *Vibhakar Shukla (03/05/2016 01:56 PM IDT)
• *Arnab Bose (04/05/2016 01:07 AM IDT)
• Radu-Alexandru Todor (04/05/2016 02:04 AM IDT)
• Shirish Chinchalkar (04/05/2016 04:55 AM IDT)
• Yan-Wu He (04/05/2016 05:09 AM IDT)
• *Gary M. Gerken (04/05/2016 05:19 AM IDT)
• Lorenz Reichel (04/05/2016 12:38 PM IDT)
• Alon Elhanati (04/05/2016 12:42 PM IDT)
• Bryce Fore (04/05/2016 06:22 PM IDT)
• Tariq Ramlall (04/05/2016 08:29 PM IDT)
• *Roberto Tauraso (04/05/2016 11:55 PM IDT)
• Jacob Levinson (05/05/2016 12:34 AM IDT)
• *Peter Gerritson (05/05/2016 01:57 AM IDT)
• Clive Tong (05/05/2016 09:28 AM IDT)
• Alex Fleischer (05/05/2016 05:48 PM IDT)
• Edward Chu (05/05/2016 06:32 PM IDT)
• *Lavanya Kannan (06/05/2016 07:45 AM IDT)
• **Siddharth Joshi (06/05/2016 03:07 PM IDT)
• Simon Uritsky (06/05/2016 11:27 PM IDT)
• *Adrian Toncean (07/05/2016 07:50 PM IDT)
• *Igor Karp (08/05/2016 05:56 AM IDT)
• Cameron Ritson (09/05/2016 05:09 PM IDT)
• *Stefano Leucci (09/05/2016 07:24 PM IDT)
• Jesse Rearick (10/05/2016 02:40 AM IDT)
• *Leandro Araújo (10/05/2016 11:07 AM IDT)
• **Tom Sirgedas (10/05/2016 06:07 PM IDT)
• Oleg Bogatchev (11/05/2016 12:55 AM IDT)
• Daniel Chong Jyh Tar (11/05/2016 09:52 AM IDT)
• *Liubing Yu (11/05/2016 10:52 AM IDT)
• *Mark Beliaev (13/05/2016 12:00 AM IDT)
• Hao Zheng (13/05/2016 03:05 PM IDT)
• *Félix Breton (13/05/2016 05:39 PM IDT)
• **Adrian Neacsu (13/05/2016 10:37 PM IDT)
• **Christof Mroz (14/05/2016 03:01 AM IDT)
• Joshua Durham (16/05/2016 09:54 PM IDT)
• **Paolo Farinelli (17/05/2016 07:31 PM IDT)
• **Wilder Boyden (18/05/2016 07:14 AM IDT)
• **Peter Huggins (19/05/2016 10:49 AM IDT)
• *Florian Fischer (21/05/2016 12:27 AM IDT)
• *Sergey Koposov (25/05/2016 06:58 PM IDT)
• *Pål Hermunn Johansen (27/05/2016 02:59 PM IDT)
• Vladimir Dorofeev (28/05/2016 02:30 PM IDT)
• **Casey Mihaloew (28/05/2016 05:28 PM IDT)
• **Andreas Stiller (28/05/2016 09:37 PM IDT)
• Erik Wünstel (31/05/2016 09:55 PM IDT)
• David Greer (01/06/2016 11:04 AM IDT)