16
$\begingroup$

You may only use pieces in the original set, and all your pieces must be the same color. The king is not allowed. Pawns do not get promoted. Pieces do not control the square they occupy.

Accepted Answer goes to the person that has the least score.

Piece cost:

  • Pawn - 1
  • Knight - 3
  • Bishop - 3
  • Rook - 5
  • Queen - 9
Improve this question
$\endgroup$
38
  • 1
    $\begingroup$ That's... Unreasonable. They are still puzzles -_- $\endgroup$
    – warspyking
    Commented Oct 14, 2014 at 0:53
  • 1
    $\begingroup$ Yep, and they are tricky logic-based, constraint satisfaction puzzles - they aren't riddles however. Maybe you could try to pitch it as a riddle. Good night! $\endgroup$
    – d'alar'cop
    Commented Oct 14, 2014 at 0:54
  • 4
    $\begingroup$ e.g. give the knight a character and personality... the are bounding across the kingdom as spies. some of the spies are double-agents so you don't want to encounter any of your own team - now it sounds less like a dry chess position where knight can't attack eachother $\endgroup$
    – d'alar'cop
    Commented Oct 14, 2014 at 1:07
  • 1
    $\begingroup$ @justhalf: But if the original set cannot control the whole board, you pay for each piece you add. This restriction forces people out of uniform solutions based on lots of bishops. I don't have an answer, but think it is a good puzzle for that reason. $\endgroup$
    – Ross Millikan
    Commented Oct 14, 2014 at 3:04
  • 4
    $\begingroup$ What do you mean by "You may not use any less than the original set."? $\endgroup$
    – IQAndreas
    Commented Oct 14, 2014 at 6:13

5 Answers 5

Reset to default
17
$\begingroup$

I think I've found a cost-33 solution:

Cost-33

As far as I can tell it's valid, but I've been staring at it for so long that I kind of don't trust myself anymore... so if you see a mistake, please tell me.

Improve this answer
$\endgroup$
7
  • $\begingroup$ New Accepted Answer! Great job! I wonder if less than 33 is possible. What do you think @d'alar'cop $\endgroup$
    – warspyking
    Commented Oct 17, 2014 at 20:16
  • $\begingroup$ Do you think it's possible to beat 33? $\endgroup$
    – d'alar'cop
    Commented Oct 18, 2014 at 4:45
  • 2
    $\begingroup$ Thanks guys. I don't think less than 33 is possible... this configuration has several pieces (Queen, a Bishop and a Rook) covering its maximum nr of squares, plus several paws that cover 2 squares that wouldn't otherwise be covered. But then again, it only requires one less pawn for a better solution :) $\endgroup$
    – Leon Bouquiet
    Commented Oct 18, 2014 at 7:48
  • $\begingroup$ I confirm that 33 is optimal. $\endgroup$
    – RobPratt
    Commented Feb 11, 2021 at 3:27
  • $\begingroup$ @RobPratt , on what basis are you saying that 33 is optimal ? What is the proof, if any ? $\endgroup$
    – Hemant Agarwal
    Commented Jun 23, 2021 at 20:04
12
$\begingroup$

The best I've got at the moment is a cost-34 solution:

enter image description here

Due to clarifications, I have found a cost-35 solution that uses the pieces from one side (no king):

enter image description here

It was surprisingly hard, and I'd really like to see better.

Old answer:

I have a solution (no restriction on pieces - only goal is to minimise cost) that costs 30. It is actually from wikipedia:

enter image description here

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ This does not use the full original set of pieces as asked. $\endgroup$
    – Ross Millikan
    Commented Oct 14, 2014 at 2:50
  • 2
    $\begingroup$ The problem is OP also said "Accepted Answer goes to the person that has the least score", which implies that not every piece should be used. $\endgroup$
    – justhalf
    Commented Oct 14, 2014 at 3:00
  • $\begingroup$ You have the best answer so far! Is it possible to get a score of 34? $\endgroup$
    – warspyking
    Commented Oct 14, 2014 at 22:43
  • $\begingroup$ @warspyking I think it is possible to beat this solution. so I think 34 is possible.. but I cannot find it just now $\endgroup$
    – d'alar'cop
    Commented Oct 14, 2014 at 22:50
  • $\begingroup$ @d'alar'cop: Btw, where do you create your image? It's good if we can have the same tool to generate the images :) $\endgroup$
    – justhalf
    Commented Oct 15, 2014 at 2:28
8
$\begingroup$

Update: So I ran a nearly exhaustive programmatic search. I excluded cases which put Queen or Bishop on the edge of the board, or a Rook on the same rank/file as the Queen or other Rook. Assuming correct code, I could not find any better than cost-33.

I found that @LeonBouquiet's solution is one of 18 distinct cost-33 solutions up to symmetry with a legal position (no pawns on first rank, no bishops on same colour), though they come in nine pairs differing by a single pawn. Including illegal positions, I found 32 cost-33 boards with distinct major piece configurations. This was much more than I had expected, and was then further surprised that given this number there were no cost-32 solutions. First, I'll show the solutions, then talk a bit lot about the algorithm I coded.

Solutions

In case you want still want to give it a go, here's an interesting hint. There are one or more piece placements that are common to all solutions with a legal position. Assuming the Queen to be on the right half:

Ra1, Nd5, c6, and a further two common to all but one of the pawn-pair solutions: c2, c4

And the full solutions (up to symmetry):

Note: black pawns represent alternate pawn placements, and hopefully my brain worked as I had to manually reconstruct pawn placements.

Four solutions using only one rook and seven pawns:
One rook, seven pawns 1One rook, seven pawns 2

And then twelve very similar solutions using only one bishop, one knight, and all eight pawns:

One b One n Eight p 1One b One n Eight p 2

One b One n Eight p 3One b One n Eight p 4

One b One n Eight p 5

The remaining two solutions which remove a knight and use 5 pawns I'll not repeat - see @LeonBouquiet's solution, noting that the f7 pawn can just as well be on h7.

Among the illegal position solutions, the most interesting one I found was this one, which barely uses the bishops:

illegal position solution
Only one is used and it's just covering 3 squares not already covered by other pieces. This leads me to believe that my filter against Bishops and Queens being on the edge of the board could indeed have filtered out valid solutions.

Algorithm

I've uploaded my C# code to GitHub. First I'll note the pawns were a bit of an after-thought. While I did eventually add them to the code, it still outputs just the major pieces so I had to manually fill in the pawns afterwards to get the solutions. I did double-check the solutions though to make sure that I didn't miss any cost-32 solutions, but I'll probably re-verify in the future as I continue to tinker with the code.

I started to code this algorithm when I realized that the number of possible configurations of major pieces might actually be feasibly computable (with all 7 major pieces on the board, there are just under 196 billion possibilities). Then, my plan was to strategically place the pawns 1-by-1 and abort evaluating the board if pawn placement was impossible. Determining impossibility is mainly that the amount of remaining pawns (given the target cost) could not cover the remaining unattacked squares. This strategy ended up working as I only had to fully evaluate roughly 1 board with pawns for every 10 boards without pawns. The core pseudocode:

loop foreach candidate major piece board:
    call EvaluateBoard with this board
    if success then: celebrate
end loop

function EvaluateBoard:

    Determine attacked squares

    if all squares are attacked then: exit with success
    if pawn placement impossible then: exit with failure

    add one pawn such that it attacks a previously unattacked square
    call EvaluateBoard with this new board

end function

Old manual cost-34 for posterity

Chess puzzle 34

Improve this answer
$\endgroup$
4
  • $\begingroup$ Great job! But @d'alar'cop is trying to beat you. $\endgroup$
    – warspyking
    Commented Oct 16, 2014 at 14:46
  • $\begingroup$ There is a lower. (Astrotrain right now) $\endgroup$
    – kaine
    Commented Oct 17, 2014 at 14:43
  • $\begingroup$ Your 34-peice solution has only one flaw (not addressed by the question) and it's this: How do you get the pawn into that corner? $\endgroup$
    – Zibbobz
    Commented Oct 17, 2014 at 19:46
  • $\begingroup$ @kaine I noticed, which is cool 'cause I was always just short of managing 33. I don't think it's beatable, but when I have time (life got busy), I'm going to attempt to find another 33 solution. $\endgroup$
    – DPenner1
    Commented Oct 22, 2014 at 1:41
3
$\begingroup$

I found a nice solution, which definitely isn't perfect, but could evolve in a game (only pieces of one colour):

Ra8 Rh1 Qc3 Bd4 Bd5 Ne4 Ng3 Kf3 and pawns on c4, d6, e6, f5

 +--+--+--+--+--+--+--+--+
8|R*|  |  |  |  |  |  |  |
 +--+--+--+--+--+--+--+--+
7|  |  |  |  |  |  |  |  |
 +--+--+--+--+--+--+--+--+
6|  |  |  |p*|p*|  |  |  |
 +--+--+--+--+--+--+--+--+
5|  |  |  |B*|  |p*|  |  |
 +--+--+--+--+--+--+--+--+
4|  |  |p*|B*|N*|  |  |  |
 +--+--+--+--+--+--+--+--+
3|  |  |Q*|  |  |K*|N*|  |
 +--+--+--+--+--+--+--+--+
2|  |  |  |  |  |  |  |  |
 +--+--+--+--+--+--+--+--+
1|  |  |  |  |  |  |  |R*|
 +--+--+--+--+--+--+--+--+
  a  b  c  d  e  f  g  h

As I said, it isn't perfect, the score is 35 (39 - 4) and the King plays an active role in protecting g2 and g4. Still, assuming white pieces, the black king has nowhere to go.

After making the rules better understandable, and shooting the king, I have another solution that fits. Since the King is definitely more powerful than a pawn, albeit more vulnerable, I had to add a few pawns but could eliminate a knight.

Pieces are:

Ra8 Rh1 Qc3 Nc7 Be3 Bf3 and pawns on c5, d2, d6, e2, e6, f2, f5, g4

 +--+--+--+--+--+--+--+--+
8|R*|  |  |  |  |  |  |  |
 +--+--+--+--+--+--+--+--+
7|  |  |N*|  |  |  |  |  |
 +--+--+--+--+--+--+--+--+
6|  |  |  |p*|p*|  |  |  |
 +--+--+--+--+--+--+--+--+
5|  |  |p*|  |  |p*|  |  |
 +--+--+--+--+--+--+--+--+
4|  |  |  |  |  |  |p*|  |
 +--+--+--+--+--+--+--+--+
3|  |  |Q*|  |B*|B*|  |  |
 +--+--+--+--+--+--+--+--+
2|  |  |  |p*|p*|p*|  |  |
 +--+--+--+--+--+--+--+--+
1|  |  |  |  |  |  |  |R*|
 +--+--+--+--+--+--+--+--+
  a  b  c  d  e  f  g  h

This makes a score of 36 (39 - 3). Not a dream score but better than nothing.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Nice, but the king didn't have a score, it cannot be used. $\endgroup$
    – warspyking
    Commented Oct 14, 2014 at 18:16
  • $\begingroup$ @warspyking well, the entire challenge is a bit ambigious. At least it was as I searched for this solution. Every time I play chess, I have a King in my standard set and it is very well known that the King can play an important role in mating the opponent. (Try to mate an opponent with Q without K, just as a challenge). You changed the written rules (probably not the rules in your head), so I'll search for another solution and add it to this one. I still think it's nice. :-) $\endgroup$
    – Ronald
    Commented Oct 14, 2014 at 18:28
  • $\begingroup$ Alright then :D Sorry about the confusion, the king had no score so I thought it was sorta implied. $\endgroup$
    – warspyking
    Commented Oct 14, 2014 at 18:37
  • $\begingroup$ So far you've got the best answer, well done! $\endgroup$
    – warspyking
    Commented Oct 14, 2014 at 18:59
  • 1
    $\begingroup$ well, actually it is (strictly speaking) the only answer (at the moment). The question is: should I feel flattered? ;-) $\endgroup$
    – Ronald
    Commented Oct 14, 2014 at 19:01
1
$\begingroup$

Invalid answer, need to be updated to conform with latest edits in the question

I found some other solutions which cost 30. I'm posting this in the hope someone else can improve any of these =)

Cost-30-attack-all-squares Cost-30-attack-all-squares-2 Cost-30-attack-all-squares-3

I found a near-solution which costs 28 (A6 and H6 are not covered):

Cost-28-attack-nearly-all-squares

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ nice. I reckon we can beat 30 $\endgroup$
    – d'alar'cop
    Commented Oct 14, 2014 at 2:41
  • 1
    $\begingroup$ This does not use the full original set of pieces as asked. A full set is 39, so we can't beat that. $\endgroup$
    – Ross Millikan
    Commented Oct 14, 2014 at 2:52
  • 1
    $\begingroup$ This is a great answer, and I really like it, however there are some clarifications you should look at, thanks for understanding. $\endgroup$
    – warspyking
    Commented Oct 14, 2014 at 22:49
  • $\begingroup$ Ok, will edit later. $\endgroup$
    – justhalf
    Commented Oct 15, 2014 at 2:28

Not the answer you're looking for? Browse other questions tagged or ask your own question.