Chess Compress
As a 14 year old boy, so in the year 1971+14=1985, my parents donated me a subscription to “Kijk”, which on its cover, in Dutch, called itself “Populair Wetenschappelijk Maandblad”. This translates as “popular science magazine” rather than “popular scientific magazine”, as it wasn’t so much trying to boast about its high subscription levels but was aiming to awaken interest with readers in general scientific and engineering topics. As for me, it managed to do so.
One month, I must have been 15, Kijk published a challenge that intrigued me. It was about trying to place as many chess pieces on a board without any being able to catch any other. You were allowed an unlimited amount (or 64 if you want) of pieces of each type. However, pawns do not participate.
Clearly, if the weight by which you count would be 1 for each type, you’d just put 32 knights on all squares of a chosen color (either black or white) and be done and the score would be 32.
However, instead, each piece is counted with a certain weight depending on its type only. This type weight is equal to one over the number of pieces of that type only you could put on the board without any of the pieces being able to catch any other piece. So a queen would get 1/8 points, as one can put maximum 8 queens on a board without any queen threatening any other queen. The “Eight Queens” problem is in fact quite well known. See https://en.wikipedia.org/wiki/Eight_queens_puzzle.
A king gets 1/16 points, a rook 1/8 points, a bishop 1/14 points and a knight 1/32 points. The idea of the weights scaling is that, the more ‘powerful’ a piece is, the fewer one can typically collect on a board and so the harder it is to get many of them, so the higher the reward must be to fit more of them on the final problem. Fitting 8 queens results in a score of 8 1/8 = 1 but fitting 8 kings only results in a score of 8 1/16 = 1/2.
I puzzled a bit and my dad also helped and then we wrote a letter back to Kijk, which I still remember contained the hand-waving sentence that “Surely, the best solution could not possibly be much better than ours.” A feeling of uncertainty about that claim stuck … until now, when we actually have some tools and some time to find a better solution and also possibly prove its optimality.
I still have all my Kijk magazines at home, bundled in 3 dark blue hard covers, one per year, which you got when you extended your membership with a year. I should look for the issue that published the results of that contest. I only remember there were quite some people that beat us at it which higher scores. So much for the hand-waving argument. But before looking things up, let’s try with a IP (Integer Programming) solver and solve this gem of a challenge to optimality. :)
