IBM Research | Ponder This | October 2003 challenges
Skip to main content

Ponder This

October 2003

<<September October November>>

Ponder This Challenge:

The following problem is sugessted by Norbert Sepp, Kalman Sallai and Gyozo Nagy. It is closely related to 2003 August Challenge.

Imagine that we define new chess pieces, with new powers.
Each piece has an associated "hit matrix" with 15 columns and 15 rows.
For example the following matrix defines the traditional rook.

0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 R 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0


To interpret this matrix: if the rook were at the center (labelled "R"), any piece at a square labelled "1" would be attacked by the rook,
but a piece at a square labelled "0" would not be attacked.
To decide whether a rook attacks a square on an 8 by 8 chessboard, we superimpose the chessboard on this matrix so that the rook is on the "R",
and look at the corresponding square.
In that sense a rook's power is independent of position: if a rook at a4 attacks a piece two squares to the right, then a rook at b7 also attacks a piece two square to the right.

With that in mind, we can define a new chess piece by writing such a 15 by 15 matrix of 0's and 1's (with the piece at the center).
In fact we can define 2^224 different kinds of piece. (Of the 225 entries in the matrix, only the central one is irrelevant.)

For each such chess piece, we define its "value" as follows:
Given a piece of type F, suppose that the largest number of such pieces that can be placed on the 8x8 board without attacking each other, is k.
Then a piece of type F has value 1/k.

Our goal is to define a number of new pieces, and place them on the 8x8 board without attacking each other.
We want to maximize the total value of the pieces on the board.

An example follows:

Define a piece F by the matrix 

0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 F 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1


Such a piece F can attack anything in any column to its right, or anything above it on its own column.
Its value is 1, since no two F pieces can be placed on the board without one attacking the other.

Similarly define G by 

1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 G 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0 0 0 0 0 0 0


G also has value 1.

Then the following 8x8 board would have value 2.75 = (6/8) + (1) + (1). It has one each of the new G and F pieces, along with 6 rooks (value=1/8).

G 0 0 0 0 0 0 0
0 R 0 0 0 0 0 0
0 0 R 0 0 0 0 0
0 0 0 R 0 0 0 0
0 0 0 0 R 0 0 0
0 0 0 0 0 R 0 0
0 0 0 0 0 0 R 0
0 0 0 0 0 0 0 F


To save time and space, this board could be abbreviated as follows:

Value = 2.75

1 0 0 0 0 0 0 0
0 8 0 0 0 0 0 0
0 0 8 0 0 0 0 0
0 0 0 8 0 0 0 0
0 0 0 0 8 0 0 0
0 0 0 0 0 8 0 0
0 0 0 0 0 0 8 0
0 0 0 0 0 0 0 1


That is, an 8 by 8 array of integers, with 0 denoting an empty square, and a positive integer k denoting a piece with value 1/k (because a maximum of k copies of that particular piece could be placed on the board).

Problem: design a collection of pieces, place them on the board, obtain a value larger than 20, and send to us the value and the 8x8 board in the format shown above (in red); that is, only the value and the 8 by 8 array of integers. No "attachments", please, and no hit matrices. We will post the names of solvers who obtain values larger than 20, as well as a running score of the maximum reported value.

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

  

Challenge: 10/03/03 @ 01:00 PM ET
Solution: 10/30/03 @ 01:00 PM ET
List Updated:

People who answered correctly:

Joe Fendel (10.3.2003 @02:13:48 PM EDT)

Nathaniel Alan Litton (10.3.2003 @03:58:02 PM EDT)
Venkata Ramayya (10.4.2003 @07:31:39 AM EDT)
Gabi Zuniga (10.4.2003 @03:46:51 PM EDT)
Patrick J. LoPresti (10.4.2003 @04:45:13 PM EDT)
Victor Chang (10.4.2003 @09:07:19 PM EDT)
Jayavel Sounderpandian (10.5.2003 @06:50:09 AM EDT)
IQSTAR (10.5.2003 @09:52:18 AM EDT)
Checn Li (10.5.2003 @03:35:07 PM EDT)
Steve Plate (10.5.2003 @04:39:05 PM EDT)
Surya Prakash (10.6.2003 @04:03:05 AM EDT)
Daniel Wood (10.6.2003 @05:22:11 AM EDT)
Bartha Daniela Cristina (10.6.2003 @09:33:09 AM EDT)
Daniel Bitin (10.6.2003 @09:56:53 AM EDT)
Amos Guler (10.6.2003 @11:45:11 AM EDT)
Ken Crounse (10.6.2003 @03:13:03 PM EDT)
Algirdas Rascius (10.6.2003 @05:04:23 PM EDT)
John G. Fletcher (10.6.2003 @08:11:36 PM EDT)
Alex Wagner (10.6.2003 @11:20:38 PM EDT)
Dmitry Litvinenko (10.7.2003 @04:22:40 AM EDT)
Chris Hills (10.7.2003 @08:36:49 AM EDT)
Niraj Jha (10.7.2003 @10:35:57 AM EDT)
Sasha Ravsky (10.7.2003 @09:26:00 AM EDT)
Mark Stubbings (10.7.2003 @10:28:04 AM EDT)
Srinivasan Ramasubramanian (10.7.2003 @11:46:30 AM EDT)
Clive Tong (10.7.2003 @02:54:49 PM EDT)
Kalyana Chakravarthy S (10.7.2003 @09:12:11 PM EDT)
Matt Smith (10.8.2003 @02:50:16 AM EDT)
Miguel Cuartas (10.8.2003 @04:33:25 AM EDT)
Rakesh Midha (10.8.2003 @06:33:00 AM EDT)
Lakshaman Parihar (10.9.2003 @02:02:00 AM EDT)
Hannu Eloranta (10.9.2003 @09:03:56 AM EDT)
Renata Pacheco (10.9.2003 @06:55:37 PM EDT)
Hagen von Eitzen (10.10.2003 @10:51:50 AM EDT)
Yury Makarychev (10.10.2003 @11:16:11 AM EDT)
Joe Moore (10.10.2003 @08:40:30 PM EDT)
Mat Hostetter (10.11.2003 @08:26:59 PM EDT)
Sasha Ravsky and Gyozo Nagy (10.12.2003 @08:18:00 AM EDT)
Sebastian Egner (10.12.2003 @01:26:58 PM EDT)
Samuli Larvala (10.12.2003 @04:04:23 PM EDT)
Ricardo Franco Moura (10.12.2003 @07:27:23 PM EDT)
John Tromp (10.13.2003 @04:56:19 AM EDT)
Jens Voß (10.13.2003 @07:23:18 AM EDT)
Charles A Stewart (10.13.2003 @06:53:54 PM EDT)
Bertram Felgenhauer (10.14.2003 @11:46:55 AM EDT)
Ameet Sharma (10.15.2003 @05:08:42 PM EDT)
Tonci Antunovic (10.16.2003 @05:08:17 PM EDT)
Luke Pebody (10.16.2003 @05:35:15 PM EDT)
David Friedman (10.20.2003 @11:11:10 AM EDT)
Hassan Masum (10.23.2003 @06:16:25 PM EDT)
Matt McCutchen (10.26.2003 @05:41:28 PM EDT)
Dan Dima (10.27.2003 @06:41:20 AM EDT)
Peter Huggins (10.27.2003 @04:18:34 PM EDT)
zelealem (10.28.2003 @10:53:15 AM EDT)
Alex Tikhonov (10.28.2003 @10:37:17 PM EDT)
Stephen Lesko (10.30.2003 @05:52:36 PM EDT)
Fakrudeen Ali Ahmed (10.31.2003 @02:36:50 PM EDT)
Coserea Gheorghe (11.01.2003 @04:58:29 PM EDT)

High Score:
28.3333 - Patrick J. LoPresti, Mat Hostetter, Sasha Ravsky and Gyozo Nagy, Sebastian Egner, Bertram Felgenhauer, Luke Pebody, Daniel Bitin

Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.