15

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
RobPratt
  • 13,685
  • 1
  • 29
  • 56
warspyking
  • 14,500
  • 10
  • 78
  • 144
  • someone really dislikes these chess puzzles – d'alar'cop Oct 14 '14 at 00:51
  • @d'alar'cop Who? – warspyking Oct 14 '14 at 00:52
  • I don't know but they downvote everything to do with chess... (they just removed their downvote on this question) – d'alar'cop Oct 14 '14 at 00:52
  • 1
    That's... Unreasonable. They are still puzzles -_- – warspyking Oct 14 '14 at 00:53
  • 1
    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! – d'alar'cop Oct 14 '14 at 00:54
  • @d'alar How do you suppose I do that? – warspyking Oct 14 '14 at 01:05
  • 4
    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 – d'alar'cop Oct 14 '14 at 01:07
  • Can we use black pawn and white pawn? They attack differently. – justhalf Oct 14 '14 at 01:54
  • Can you allow us to use the King? – justhalf Oct 14 '14 at 02:32
  • I think this is an excellent puzzle. Well defined goal, rules, and scoring (though the two answers so far fail using all the normal set of pieces.) – Ross Millikan Oct 14 '14 at 02:49
  • @RossMillikan: 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, otherwise everyone has the same score! Also the question title is "How many chess pieces are needed". Perhaps OP needs to clarify the first sentence. – justhalf Oct 14 '14 at 03:00
  • 1
    @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. – Ross Millikan Oct 14 '14 at 03:04
  • 1
    That sounds weird, especially considering that this question comes from his comment on this question, in which there is a solution using the complete set, and that OP pointed out that there are unneeded pieces. Let's wait for OP to wake up then :) – justhalf Oct 14 '14 at 03:06
  • 4
    What do you mean by "You may not use any less than the original set."? – IQAndreas Oct 14 '14 at 06:13
  • @RossMillikan: A solution using the complete set of pieces seems academic. With 4 rooks and two queens you're mostly done. I read "You may not use any less than the original set" as "you may not use any piece that is not in the original set" - the question remains if you are allowed to use more pieces than the original set; if not, solutions with more than 4 bishops would be illegal. – oerkelens Oct 14 '14 at 12:56
  • hey warspy, shall we modify the question to make it fit the spirit of the answers? (ie lift the restriction about using a side or less - which is unclear based on all the activity anyway) – d'alar'cop Oct 14 '14 at 17:41
  • what about promoted pawns? my answer still works if promoted pawns are allowed – d'alar'cop Oct 14 '14 at 17:57
  • @d'alar'cop I just realized how much confusion there was after getting back from school. It took me hours to realize this and now some answers are incorrect, I really messed up a good puzzle didn't I? – warspyking Oct 14 '14 at 17:58
  • @d'alar I should probably clarify that you cannot promote pawns, that would result in people making like 8 rooks. – warspyking Oct 14 '14 at 18:00
  • well it may still work because you still want to minimise points (8 rooks is losing). franjly I think minimising points is interesting enough... it also happens to be what everyone is already doing – d'alar'cop Oct 14 '14 at 18:02
  • great, now all current answers are wrong :p – d'alar'cop Oct 14 '14 at 18:08
  • True... Maybe I should remove that requirement? Although I kinda wanted an answer to this. – warspyking Oct 14 '14 at 18:09
  • @d'alar'cop Should I remove that requirement? – warspyking Oct 14 '14 at 18:10
  • maybe just leave it and leave a little apology in the question. then upvote the guy who did it properly – d'alar'cop Oct 14 '14 at 18:12
  • @d'alar Would it be wrong to try and answer it myself to give others an idea? This is a Q&A site. – warspyking Oct 14 '14 at 18:51
  • not at all. if you have an answer put it up. – d'alar'cop Oct 14 '14 at 18:52
  • By "not any more than the average set", do you mean that you can't use more than 4 rooks(2 white, 2 black), 4 bishops, etc.? i.e., is the 30-cost Bishop solution valid? – YenTheFirst Oct 14 '14 at 19:02
  • @Yen Only 1 colour set was implied. – warspyking Oct 14 '14 at 19:29
  • so, then, do you mean that you can't use more than 2 rooks, 2 bishops, etc.? – YenTheFirst Oct 14 '14 at 19:56
  • Exactly, you want to clarify anything else for others? – warspyking Oct 14 '14 at 20:38
  • @warspyking: Perhaps you can create another question to contain all the answers for previous interpretation of your question? It seems possible to have a score less than 30 in that, I would like to see it improved. =) – justhalf Oct 15 '14 at 02:33
  • @justhalf http://puzzling.stackexchange.com/questions/2907/how-many-chess-pieces-are-needed-to-control-every-square-on-the-board-no-piece – warspyking Oct 15 '14 at 09:45
  • Does a single color need to control the board, or can one color control a portion of the board, with the other color covering the remaining locations? – Matthew0898 Aug 24 '15 at 17:38
  • @Matthew0898 "and all your pieces must be the same color." – warspyking Aug 24 '15 at 17:43
  • Is "Pieces do not control the square they occupy" intended to allow pawns to control the square they occupy? If not, it should say "*Men do not control the square they occupy*". – Peter Taylor Aug 24 '15 at 17:54
  • @Peter Taylor A pawn is a piece. – warspyking Aug 24 '15 at 17:57
  • Not universally, whereas man is unambiguous. – Peter Taylor Aug 24 '15 at 18:48
  • @Peter Taylor A chess piece should be a physical piece. Idk, maybe it's just me, but I don't call my pawn a "man". – warspyking Aug 24 '15 at 18:50

5 Answers5

17

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.

Leon Bouquiet
  • 296
  • 1
  • 2
  • New Accepted Answer! Great job! I wonder if less than 33 is possible. What do you think @d'alar'cop – warspyking Oct 17 '14 at 20:16
  • Do you think it's possible to beat 33? – d'alar'cop Oct 18 '14 at 04:45
  • 2
    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 :) – Leon Bouquiet Oct 18 '14 at 07:48
  • I confirm that 33 is optimal. – RobPratt Feb 11 '21 at 03:27
  • @RobPratt , on what basis are you saying that 33 is optimal ? What is the proof, if any ? – Hemant Agarwal Jun 23 '21 at 20:04
  • @HemantAgarwal I used mixed integer linear programming to confirm optimality. I did the same for this closely related question: https://puzzling.stackexchange.com/questions/2907/how-many-chess-pieces-are-needed-to-control-every-square-on-the-board-no-piece – RobPratt Jun 23 '21 at 20:32
  • For what it's worth, I can second RobPratt's claim: A few years back I took a second crack at this question with an exhaustive programmatic search (mostly, I had to manually specify major piece sets). I found a surprising number of cost-33 solutions, but no cost-32 solutions (though only 3 further distinct major piece placements with a legal chess position, and two of those only differed by a single bishop). When time permits, I'll see about cleaning up the code and throwing it on GitHub. Most interesting solution I found is that there turned out to be a no knights cost-33 solution. – DPenner1 Jun 29 '23 at 20:20
12

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

d'alar'cop
  • 12,892
  • 4
  • 49
  • 90
  • 1
    This does not use the full original set of pieces as asked. – Ross Millikan Oct 14 '14 at 02:50
  • 2
    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. – justhalf Oct 14 '14 at 03:00
  • You have the best answer so far! Is it possible to get a score of 34? – warspyking Oct 14 '14 at 22:43
  • @warspyking I think it is possible to beat this solution. so I think 34 is possible.. but I cannot find it just now – d'alar'cop Oct 14 '14 at 22:50
  • @d'alar'cop: Btw, where do you create your image? It's good if we can have the same tool to generate the images :) – justhalf Oct 15 '14 at 02:28
  • @justhalf I use WinBoard if I'm on Windows and XBoard if I'm on Linux - then I use a Snipping Tool (Shutter in Linux) to only get the board. They are so similar that I can't tell anymore which one I used for this question :p – d'alar'cop Oct 15 '14 at 02:40
  • Ah, I thought there were some online tool which can give you the image directly. I'm using this tool and use Mac screen capture, but I'm looking for something better. Preferably something which can display the attacked spots =p – justhalf Oct 15 '14 at 02:44
  • @justhalf yes I wanted that as well... as an assistant for me more than as a presentation tool. I decided it's better practice for us not to use such aides – d'alar'cop Oct 15 '14 at 02:45
  • New best answer available. Try to beat it? – warspyking Oct 17 '14 at 21:16
8

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

DPenner1
  • 191
  • 6
  • Great job! But @d'alar'cop is trying to beat you. – warspyking Oct 16 '14 at 14:46
  • There is a lower. (Astrotrain right now) – kaine Oct 17 '14 at 14:43
  • 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? – Zibbobz Oct 17 '14 at 19:46
  • @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. – DPenner1 Oct 22 '14 at 01:41
3

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.

Ronald
  • 131
  • 4
  • Nice, but the king didn't have a score, it cannot be used. – warspyking Oct 14 '14 at 18:16
  • @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. :-) – Ronald Oct 14 '14 at 18:28
  • Alright then :D Sorry about the confusion, the king had no score so I thought it was sorta implied. – warspyking Oct 14 '14 at 18:37
  • So far you've got the best answer, well done! – warspyking Oct 14 '14 at 18:59
  • 1
    well, actually it is (strictly speaking) the only answer (at the moment). The question is: should I feel flattered? ;-) – Ronald Oct 14 '14 at 19:01
  • I was kinda hoping you would. d'alar'cop has beaten you with a score of 35! Can you beat that? – warspyking Oct 14 '14 at 22:44
  • Oh and use @war please, i never noticed this comment for the longest time. – warspyking Oct 14 '14 at 22:45
  • @warspyking I'll have a look at it tonight. Today I'm out of office. My current solution is better in the respect that it is a situation that can be reached in a game. But since that isn't a requirement, d'alar'cop is definitely better now. It'll be hard to beat, but I'll try nevertheless. – Ronald Oct 15 '14 at 05:16
  • @warspyking Oh, and I was proud of my result, don't worry. But empty sets and sets with only 1 element are always some sort of challenge to produce good looking statements that don't really state something. Every married person can say: "you're the best spouse I have", even if that person is among the most awful in the world. But that's why I used the ";-)" – Ronald Oct 15 '14 at 06:57
1

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

justhalf
  • 6,014
  • 2
  • 31
  • 49