Tuesday, 28 January 2014

chess - Biggest army on a chessboard


Reminder:


Everybody knows that we can place 8 queens in a chessboard without threatening each other (see here). Same reasoning can be applied for knights, bishops, rooks and kings. Giving respectively 32 knights, 14 bishops, 8 rooks, and 16 kings.


Problem:


If we assign to each type of piece a value inversely proportional of the number of this we can place. It means Knights = 1/32. Bishop = 1/14. Rook = 1/8. Queen = 1/8 and King = 1/16.



What is the best sum value we can achieve mixing these pieces still with none able to take each other?


Example


enter image description here


In this position we have 1 queen, 4 rooks, 1 knight and 2 kings, so the value would be 1/8 + 4/8 + 0/14 + 1/32 + 2/16 = 25/32 = 0.78125.
Can you beat that score?
Hard Question: Can you prove that your answer is optimal?


Actual High scores



@evargalo 1.2857
@keeta 1.303

@Blcknght 1.3125
@oray 1.3348 (optimal).



source: Gyozo Nagy in IBM Research Ponder this - August 2003 [found in Diophante.fr]



Answer



Here is the most probable optimal solution with some extra modification of previous answers:



enter image description here



The score is 1.3348.



Here is the brute Force Code written by @fireflame241 confirming this is actually optimal.


No comments:

Post a Comment