Ponder This Challenge - August 2003 - Non attacking chess pieces

Ponder This Challenge:

This month's chess puzzle is from Gyozo Nagy.

It is well known that exactly 8 queens can be placed on a chessboard
without attacking each other; similarly 8 rooks, or 14 bishops,
or 32 knights, or 16 kings.
What if we are allowed to mix pieces?

So assign values of 1/8 to a queen (Q); 1/8 to a rook (R);
1/14 to a bishop (B); 1/32 to a knight (N); and 1/16 to a king (K).

Problem (Part 1): Construct the most expensive army on a chessboard,
using any number of these pieces, so that no piece attacks another.
(Here "any number" includes 0.)

Problem (Part 2): Same thing, but disallowing kings (so our army
consists only of queens, rooks, bishops and knights).

Can these mixed armies achieve values greater than 1?
In each case give the largest possible value (and a setup achieving it).

For example, the following setup

would have value
1/8 + 4/8 + 0/14 + 1/32 + 2/16 = 25/32 = 0.78125.

To be listed among the correct solvers,
you need to submit both a solution for part 1 with value exceeeding 1.3,
and a solution for part 2 with value exceeding 1.06.
Extra credit if you prove optimality.

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

• Click here to view the solution

  Solution:

  Part 1:

  The setup

  K . N B N B N B
  . . . . . . . .
  K . K . K . K .
  . . . . . . . .
  K . K . K . K .
  . . . . . . . .
  N . N B N B N B
  . R . . . . . .
  

  has value = 1/8 + 6/14 + 7/32 + 9/16 = 299/224 = 1.3348

  Part 2:

  The setup

  N B . . . B B .
  . . . R . . . .
  . . R . . . . .
  B N . . . . B .
  N . . . . . N .
  . . . . . . . R
  . . . . R . . .
  B B . . . N B .
  

  has value = 4/8 + 8/14 + 5/32 = 275/224 = 1.2277...

  Naturally, our solutions do not use queens

  Several readers said they have proven optimality, either with an exhaustive search, or by using integer programming.

  ---

  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

• Jayavel Sounderpandian (8.5.2003 @06:00:50 AM EDT)
• Daniel Wood (8.5.2003 @06:49:26 AM EDT)
• Alan O'Donnell (8.5.2003 @09:56:01 AM EDT)
• Graham McHardy (8.5.2003 @11:40:15 AM EDT)
• Kurt Schneider, Walter Lehman (8.5.2003 @12:59:11 PM EDT)
• Jerold Lewandowski (8.5.2003 @01:33:58 PM EDT)
• Fr. Terry Donahue (8.5.2003 @01:52:28 PM EDT)
• David Woodruff (8.5.2003 @06:28:06 PM EDT)
• Joseph DeVincentis (8.6.2003 @12:30:34 AM EDT)
• Wei Liu (8.6.2003 @06:30:41 AM EDT)
• Mark Stubbings (8.6.2003 @09:22:00 AM EDT)
• Steve Moschkau (8.6.2003 @10:39:13 AM EDT)
• Ilan Algor (8.6.2003 @12:22:00 PM EDT)
• Joshua Fender (8.6.2003 @01:41:20 PM EDT)
• Ragini Acharya (8.6.2003 @03:16:45 PM EDT)
• Pete Camagna (8.6.2003 @05:43:00 PM EDT)
• Ashish Mishra (8.6.2003 @07:48:31 AM EDT)
• Daniel Chong Jyh Tar (8.6.2003 @10:58:24 PM EDT)
• Frank Vernaillen (8.7.2003 @08:39:48 AM EDT)
• Chris Hills (8.7.2003 @08:51:00 AM EDT)
• Hagen von Eitzen (8.7.2003 @09:33:27 AM EDT)
• Steve Clymer (8.7.2003 @10:09:38 AM EDT)
• Francis Golding (8.7.2003 @10:48:52 AM EDT)
• Projjwal Banerjee (8.7.2003 @10:58:34 AM EDT)
• John Hamilton (8.7.2003 @05:09:24 PM EDT)
• Ken Crounse (8.7.2003 @05:45:00 PM EDT)
• Philippe Fondanaiche (8.8.2003 @12:11:30 PM EDT)
• Russell Logan (8.8.2003 @09:51:42 PM EDT)
• Oliver Gronau (8.9.2003 @06:09:41 AM EDT)
• Nikhil Sahasrabudhe (8.9.2003 @08:02:03 AM EDT)
• Peter Huggins (8.9.2003 @09:11:34 PM EDT)
• Guler Amos (8.10.2003 @02:55:33 AM EDT)
• Aditya Utterwar (8.10.2003 @12:52:22 PM EDT)
• Bertram Felgenhauer (8.10.2003 @07:18:34 PM EDT)
• Klaus Hoffman (8.11.2003 @03:01:04 AM EDT)
• Victor A. Chang (8.11.2003 @03:15:06 AM EDT)
• Elizabeth Phan (8.11.2003 @07:39:45 AM EDT)
• Daniel Bitin (8.11.2003 @12:37:22 PM EDT)
• Lance Gay (8.11.2003 @01:38:41 PM EDT)
• Sorin Ostafiev (8.11.2003 @02:00:39 PM EDT)
• Felix Liao (8.11.2003 @08:27:34 PM EDT)
• Niraj Jha (8.12.2003 @12:22:59 AM EDT)
• Christie Bolton (8.12.2003 @05:34:27 AM EDT)
• Dan Florescu (8.12.2003 @05:46:00 AM EDT)
• Miguel Cuartas (8.12.2003 @01:56:14 PM EDT)
• R. Nandakumar (8.13.2003 @02:29:42 AM EDT)
• L. J. Zigerell, Jr. (8.13.2003 @10:40:27 PM EDT)
• Don Dodson (8.14.2003 @11:11:51 AM EDT)
• Mohit Sauhta (8.14.2003 @04:17:42 AM EDT)
• Nelu Cioc (8.15.2003 @06:28:27 AM EDT)
• Traian Dajma (8.15.2003 @07:54:43 AM EDT)
• Prithu B. Tiwari (8.15.2003 @08:23:00 AM EDT)
• John Ritson (8.17.2003 @11:57:43 PM EDT)
• Jean Pierre Battaille (8.18.2003 @03:50:31 AM EDT)
• Daniel A. Clymer (8.18.2003 @05:44:27 PM EDT)
• Barry Haddow (8.18.2003 @06:56:05 PM EDT)
• Clive Tong (8.19.2003 @02:58:50 AM EDT)
• Roy Murphy (8.19.2003 @05:48:12 AM EDT)
• Kurt Schneider (8.19.2003 @11:51:23 AM EDT)
• Dennis Langdeau (8.19.2003 @09:29:08 PM EDT)
• Iqstar (8.20.2003 @03:17:04 AM EDT)
• Brittany Fugitt (8.20.2003 @04:30:14 AM EDT)
• Balabhas Balasundaram (8.20.2003 @01:41:00 PM EDT)
• Ernest Woei (8.20.2003 @07:44:20 PM EDT)
• Vishal Goel (8.21.2003 @11:59:28 AM EDT)
• Karthik Lakshminarayanan (8.21.2003 @03:07:07 AM EDT)
• Claudio Baiocchi (8.24.2003 @04:35:49 AM EDT)
• Coserea Gheorghe (8.24.2003 @07:28:40 AM EDT)
• Sergio Ruiz Unican (8.24.2003 @03:06:07 PM EDT)
• Raluca Matei (8.25.2003 @05:12:14 AM EDT)
• Dmitry Latvinenko (8.25.2003 @10:01:05 AM EDT)
• David Friedman (8.25.2003 @12:26:27 PM EDT)
• Kalyana Chakravarthy S. (8.27.2003 @01:11:31 AM EDT)
• Alex Wagner (8.27.2003 @12:21:18 PM EDT)
• Gabi Zuniga (8.27.2003 @12:29:45 PM EDT)
• Brian Bitto (8.27.2003 @01:27:48 PM EDT)
• Rob Pratt (8.27.2003 @04:09:09 PM EDT)
• Jean-Marc Coutin (8.29.2003 @06:11:24 AM EDT)
• Nachiket Bapat (8.29.2003 @03:31:48 PM EDT)
• Arun Sivaramakrishnan (8.30.2003 @02:27:12 AM EDT)
• Ricky Lane (9.02.2003 @05:11:09 AM EDT)
• Peter Mattsson (9.02.2003 @10:21:49 AM EDT)
• Tarkesh Pande (9.02.2003 @07:31:17 PM EDT)
• High Scores: (None)
• Part 1: (1.3348 - Daniel Wood, Wei Liu, Pete Camagna, Chris Hills, Joshua Fender,Daniel Chong Jyh Tar,Hagen von Eitzen, John Hamilton, Ken Crounse, Oliver Gronau, Peter Huggins, Bertram Felgenhauer, Klaus Hoffman, Victor A. Chang, Daniel Bitin, Lance Gay, Sorin Ostafiev, Christie Bolton, Dan Florescu, Miguel Cuartas, Don Dodson,Nelu Cioc, Mohit Sauhta, Kurt Schneider, Dennis Langdeau, Ernest Woei, Vishal Goel, Balabhas Balasundaram, Iqstar, Claudio Baiocchi, Coserea Gheorghe, Dmitry Latvinenko, Sergio Ruiz Unican, Russell Logan, Gabi Zuniga, Alex Wagner, Rob Pratt, Jean-Marc Coutin, Arun Sivaramakrishnan, Brian Bitto, Peter Mattsson)
• Daniel Wood, Wei Liu, Pete Camagna, Chris Hills, Joshua Fender, (Daniel Chong Jyh Tar,Hagen von Eitzen, John Hamilton, Ken Crounse, Oliver Gronau, Peter Huggins, Bertram Felgenhauer, Klaus Hoffman, Victor A. Chang, Daniel Bitin, Lance Gay, Sorin Ostafiev, Christie Bolton, Dan Florescu, Miguel Cuartas, Don Dodson,Nelu Cioc, Mohit Sauhta, Kurt Schneider, Dennis Langdeau, Ernest Woei, Vishal Goel, Balabhas Balasundaram, Iqstar, Claudio Baiocchi, Coserea Gheorghe, Dmitry Latvinenko, Sergio Ruiz Unican, Russell Logan, Gabi Zuniga, Alex Wagner, Rob Pratt, Jean-Marc Coutin, Arun Sivaramakrishnan, Brian Bitto, Peter Mattsson)
• Daniel Chong Jyh Tar (,Hagen von Eitzen, John Hamilton, Ken Crounse, Oliver Gronau, Peter Huggins, Bertram Felgenhauer, Klaus Hoffman, Victor A. Chang, Daniel Bitin, Lance Gay, Sorin Ostafiev, Christie Bolton, Dan Florescu, Miguel Cuartas, Don Dodson,Nelu Cioc, Mohit Sauhta, Kurt Schneider, Dennis Langdeau, Ernest Woei, Vishal Goel, Balabhas Balasundaram, Iqstar, Claudio Baiocchi, Coserea Gheorghe, Dmitry Latvinenko, Sergio Ruiz Unican, Russell Logan, Gabi Zuniga, Alex Wagner, Rob Pratt, Jean-Marc Coutin, Arun Sivaramakrishnan, Brian Bitto, Peter Mattsson)
• Hagen von Eitzen, John Hamilton, Ken Crounse, Oliver Gronau, Peter Huggins, Bertram Felgenhauer, Klaus Hoffman, Victor A. Chang, Daniel Bitin, Lance Gay, Sorin Ostafiev, Christie Bolton, Dan Florescu, Miguel Cuartas, Don Dodson (,Nelu Cioc, Mohit Sauhta, Kurt Schneider, Dennis Langdeau, Ernest Woei, Vishal Goel, Balabhas Balasundaram, Iqstar, Claudio Baiocchi, Coserea Gheorghe, Dmitry Latvinenko, Sergio Ruiz Unican, Russell Logan, Gabi Zuniga, Alex Wagner, Rob Pratt, Jean-Marc Coutin, Arun Sivaramakrishnan, Brian Bitto, Peter Mattsson)
• Nelu Cioc (, Mohit Sauhta, Kurt Schneider, Dennis Langdeau, Ernest Woei, Vishal Goel, Balabhas Balasundaram, Iqstar, Claudio Baiocchi, Coserea Gheorghe, Dmitry Latvinenko, Sergio Ruiz Unican, Russell Logan, Gabi Zuniga, Alex Wagner, Rob Pratt, Jean-Marc Coutin, Arun Sivaramakrishnan, Brian Bitto, Peter Mattsson)
• Mohit Sauhta, Kurt Schneider, Dennis Langdeau, Ernest Woei, Vishal Goel, Balabhas Balasundaram, Iqstar, Claudio Baiocchi, Coserea Gheorghe, Dmitry Latvinenko, Sergio Ruiz Unican, Russell Logan, Gabi Zuniga, Alex Wagner, Rob Pratt, Jean-Marc Coutin, Arun Sivaramakrishnan, Brian Bitto, Peter Mattsson (None)
• Part 2: (1.2277 - Daniel Wood, Wei Liu, Joshua Fender, Hagen von Eitzen, John Hamilton,Ken Crounse, Oliver Gronau, Bertram Felgenhauer, Daniel Chong Jyh Tar, Klaus Hoffman, Philippe Fondanaiche, Daniel Bitin, Lance Gay, Sorin Ostafiev, Christie Bolton, Miguel Cuartas, Don Dodson, Kurt Schneider, Dennis Langdeau, Ernest Woei, Balabhas Balasundaram, Iqstar, Claudio Baiocchi, Coserea Gheorghe, Dmitry Latvinenko, Gabi Zuniga, Alex Wagner, Rob Pratt, Jean-Marc Coutin, Arun Sivaramakrishnan, Brian Bitto, Peter Mattsson)
• Daniel Wood, Wei Liu, Joshua Fender, Hagen von Eitzen, John Hamilton, (Ken Crounse, Oliver Gronau, Bertram Felgenhauer, Daniel Chong Jyh Tar, Klaus Hoffman, Philippe Fondanaiche, Daniel Bitin, Lance Gay, Sorin Ostafiev, Christie Bolton, Miguel Cuartas, Don Dodson, Kurt Schneider, Dennis Langdeau, Ernest Woei, Balabhas Balasundaram, Iqstar, Claudio Baiocchi, Coserea Gheorghe, Dmitry Latvinenko, Gabi Zuniga, Alex Wagner, Rob Pratt, Jean-Marc Coutin, Arun Sivaramakrishnan, Brian Bitto, Peter Mattsson)
• Ken Crounse, Oliver Gronau, Bertram Felgenhauer, Daniel Chong Jyh Tar, Klaus Hoffman, Philippe Fondanaiche, Daniel Bitin, Lance Gay, Sorin Ostafiev, Christie Bolton, Miguel Cuartas, Don Dodson, Kurt Schneider, Dennis Langdeau, Ernest Woei, Balabhas Balasundaram, Iqstar, Claudio Baiocchi, Coserea Gheorghe, Dmitry Latvinenko, Gabi Zuniga, Alex Wagner, Rob Pratt, Jean-Marc Coutin, Arun Sivaramakrishnan, Brian Bitto, Peter Mattsson (None)