Inferrence strategies for hidden pieces on a chessboard

Question

This is a potentially off-topic question, however, the reason I'm asking it here is in the hope of gaining the perspective of puzzlers in tackling such a problem. That is, I am more interested in the adopted mindset and methods for solving it as opposed to the solution of particular instance of the puzzle. That said, I understand if such questions are completely unfitting and I will gladly delete if you find it to be the case for this one too.

The puzzle*

5 chess pieces, king, bishop, knight, queen and rook are placed on 5 random squares of the chessboard. Each occupied square is highlighted but we do not know where each piece is placed.

Example of starting state of a puzzle:

Solution (pieces revealed):

The objective is to figure out where each piece lies with minimal number of questions asked.

Means of probing/gathering information. We can either ask

• Question A: How many times a given square is attacked, which can be answered with 0, 1, 2, 3, 4 or 5. The latter is the maximum and can occur only for an empty square (only empty squares can in principle be attacked by all 5 pieces).
• Question B: One can also ask if a certain piece is on a certain square, which will be answered by yes or no.

(*): Source: http://runamok.tech/cpuzzle.html

---

Thoughts on sets of squares seen by a certain piece

Given the rules according to which each piece moves, we can characterize each piece in terms of the set of squares it sees, like a "forcefield" if you could excuse the term. For instance:

• King: if not at a wall, then it sees a 3 by 3 square around itself.
• Knight: All squares of opposite color to its current square's color along the contour of a 5 by 5 square around the knight.
• Bishop: Diagonals crossing its current square.
• Rook: horizontal and vertical lines crossing its current square.
• Queen: the union of squares seen by a rook and a bishop.

Admittedly, this is all quite rough and incomplete, but I just wanted to give a more geometric description of each piece.

---

Questions:

1. The aim of the post is not necessarily to figure out the optimal way of solving it, or but rather what the possible approaches are for tackling the problem. In other words, according to what strategies could one ask the two types of questions. Intuitively, the puzzle resembles the problem of inferring the presence of objects in physics based on how they interact with their environment (e.g., detecting an astronomical object based on its gravitational effect).

2. Where to begin? Does it make sense to ask Questions A first for squares on the rim, as opposed to central squares which are more likely to be seen by a greater number of pieces? Just an idea, maybe retrograde type methods can also be applicable here.

3. Are there analogies, from mathematics, physics or other puzzles, that one could use to formulate the puzzle differently?

Answer 1

The usual heuristic for this sort of thing is that at any given point there's some number of possible solutions -- e.g., for the puzzle discussed here there are 5!=120 possible arrangements of the pieces -- and each question will, once answered, reduce that number (to the number of configurations for which that answer is correct), and you want to reduce as much as possible in the worst case. That is: for each question you could ask, consider all the possible answers and look at how many configurations are consistent with that answer. The largest number of configurations, across all answers, tells you how much you gain in the worst case when you ask your question. You want the question that makes this as small as possible.

This is only a heuristic because it isn't necessarily best to reduce the search space as much as possible on each question, because it might sometimes turn out that you do better to ask a question that leaves a set of possible configurations that's larger but somehow easier to break down further with later questions. But it's typically a very good heuristic.

Unfortunately, the calculations you need to do to apply this heuristic are pretty painful. E.g., you have 64 versions of question A (for each of which there might be as many as 6 possible answers to consider) and 25 versions of question B (for each of which there are 2 possible answers to consider) and for each of those possible questions and answers you need to check which of the 120 possible configurations are consistent with it. If you're writing a computer program, this is no problem. If you're a human trying to do this thing by hand, you really don't want to be doing that.

So the next thing to look for is ways to approximate, or just plain guess, which questions might lead to big reductions. For instance, it seems likely that type-A questions are usually better than type-B questions because a type-A question has more possible answers. (Though probably some of the possible answers correspond to very small sets of configurations; e.g., you'll hardly ever get told "all five pieces attack this square".) And questions for which the different possible answers all have about the same number of configurations leading to that answer are better, so e.g. if you're going to ask a yes/no question you want "yes" and "no" both to feel about equally likely. (Which is probably rarely going to be the case for a type-B question here, another reason why type A questions are probably usually better.) Having said that, type A questions may also have pretty unbalanced answers, and they're also harder to use because the information they give you is of a complicated sort. ("There is a queen or rook on this square, and a queen or bishop on that square, but not both.")

In this particular case, the sort of thing I think I would do is: look for squares that could be attacked by several of the pieces. For instance, d5 could be attacked by a knight on c7, or by a bishop or queen on b3 or f3. Better is f7, attackable by a rook or queen on c7/f8/f3, by a king on f8, by a bishop or queen on b3, or by a knight on h6. It feels as if answers 0 and 1 should be something like equal in "size" and a non-negligible fraction of configurations will lead to bigger numbers. Other similarly interesting squares: f4, c3.

When asking each question you ideally want to bear in mind what the answers to earlier ones have told you. For these puzzles, that can be quite hard to figure out. Another approach, at least early in the game, might be to try to ask questions that are somewhat "independent" of one another, though that's hard to judge.

I wouldn't expect there to be any neat general technique for these, and I would expect them usually to be hard work to solve if you are seriously trying not to use many more questions than you need.

I wouldn't expect analogies from physics to be very helpful. There are other games that have something of the same cutting-down-the-search-space feel, such as Mastermind or Battleship, but I'm not sure there's enough in common for strategies more specific than the sort of thing I discussed above to transfer from one to another.

If you ask only yes/no questions, and if each time you have the good fortune to find a question that divides the possible configurations into two equal parts, then you halve the number of still-possible configurations with every question, so the number of questions you need to ask in the worst case is the smallest $n$ for which $2^n$ is at least the number of configurations. (Equivalently, it's the ceiling of the base-2 logarithm of the number of configurations.) In the present case, that would be 7 questions. Of course you probably won't ask only yes/no questions, and you certainly won't be dividing the search space in half perfectly every time, but this gives you at least a rough idea of the ballpark number of questions you might need.

You can think of each answer you get as adjusting probability estimates for each piece being on each possible square. Figuring out exactly how the probabilities should change is a lot of work, but crude approximations that assume that each question gives you independent information may be useful.

Once you have enough information to be fairly confident about some of the piece positions, it's probably appropriate to try to find a piece/square combination that you're somewhere around 50% confident of, or one where you know there are only two possibilities, and ask a B-question about it. One or two B-questions with "yes" answers will cut the possibilities down enough that you can then probably do the rest rigorously without too much pain.

---

Maybe it would be interesting to walk through an attempt at this specific problem. I don't guarantee that my strategy is anything like optimal, but it's probably at least reasonably good.

I might begin by asking: how many attacks on f7? The answer turns out to be 2. So I know that exactly two of { c7 is R or Q, f8 is K or R or Q, h6 is N, b3 is B or Q, f3 is R or Q } hold. That turns out to leave us with 46 possibilities, so that was a good choice of question. It's kinda hard to get one's head around just how it cuts down the search space, though, so I would probably proceed blindly with another plausible type-A question. Maybe: how many attacks on f4? The answer turns out to be 2 again. That question on its own would have reduced the number of possibilities from 120 to 48. The two together bring the number down to 18 -- so they've behaved as if roughly "independent", which is nice. (These numbers are not meant to be obvious, or indeed feasible to figure out in your head unless you're unusually patient. They're just to give some idea of how much progress we're making.)

Both those answers are maybe "larger than expected". Maybe there's some single piece that contributes to both. A R or Q on f8 or f3 would do it; so would a Q on c7. It seems likely that we have at least one of those. (It turns out that 16 of the 18 still-possible configurations have that property. Again, I am not suggesting that you would realistically be counting these in your head when solving the problem.) So quite likely the Q is in one of those three places (it turns out this is true in 10 of the 18 cases) and therefore not on h6 or b3. Hmm, maybe it might be interesting to look at e6, which has several potential attacks but rather different ones from the ones we've probed so far? Let's ask: how many attacks on e6? The answer is 1, so exactly one of { c7 is N, f8 is N, h6 is R or Q, b3 is B or Q } holds. This on its own would have taken us from 120 to 48 possibilities; now it takes us from 18 to 5, so again we successfully found something that behaves fairly "independently". But again it's a bit hard to get one's head around what we know at this point. Let's write it down.

• 2 of RQc7, RQKf8, Nh6, BQb3, RQf3
• 2 of BQc7, RQf8, BQh6, (--), RQKf3
• 1 of Nc7, Nf8, RQh6, BQb3, (--)

and we suspect

• probably at least 1 of Qc7 RQf8, RQf3
• quite likely Q on c7, f8, or f3

It feels to me (even without the numbers that I cheatily calculated by computer) as if all three answers do better than halving the search space, maybe quite a bit better. Three halvings would give us 30 possibilities. So at this point I'd be feeling as if maybe there are 5-20 possibilities. (As it turns out, we're right at the optimistic end of that range.)

It doesn't feel as if we're ready to start asking piece-on-square questions yet; even very plausible options like Qc7 feel quite a lot more likely "no" than "yes", so those questions aren't going to be very efficient. What squares seem likely to be attacked, maybe multiple times, given the information we have? Well, b7 would be attacked by a queen on any of c7, b3, f3, and by various other possible things too. I'm a little worrying that the answer "1" is most likely and won't tell us much, but let's ask anyway. How many attacks on b7? The answer is in fact 1, and it turns out that with this we have only 2 possibilities remaining, but of course we don't know that. So now we know:

• 2 of RQc7, RQKf8, Nh6, BQb3, RQf3
• 2 of BQc7, RQf8, BQh6, (--), RQKf3
• 1 of Nc7, Nf8, RQh6, BQb3, (--)
• 1 of RQKc7, (--), (--), RQb3, BQf3

So, all the specific piece/square pairings listed above are more likely than baseline, especially the ones on the first two lines. So since we likely have BQb3 and likely have RQb3, Qb3 seems quite likely; since we likely have RQf3 and likely have BQf3, Qf3 also seems quite likely. Let's pick a square that would distinguish between those, and maybe involve some piece/square combinations we haven't explored yet. How many attacks on b5? -- We got lucky! There are two attacks on b5, which is definitely more than we had a right to expect. Now we know:

• 2 of RQc7, RQKf8, Nh6, BQb3, RQf3
• 2 of BQc7, RQf8, BQh6, (--), RQKf3
• 2 of BQKc7, (--), RQh6, RQb3, (--)
• 1 of Nc7, Nf8, RQh6, BQb3, (--)
• 1 of RQKc7, (--), (--), RQb3, BQf3

This feels like it might be getting close to enough information to nail down the answer, though in fact it turns out that that last question didn't tell us anything -- both the possibilities that were left actually have two attacks on b5! Still, it may be helpful to us even if a perfect reasoner wouldn't have gained anything from it.

Let's do something very crude and score each piece/square option. Two points for appearing in a "2 of" line, one point for appearing in a "1 of" line.

• c7: N1, B4, R3, Q7, K3.
• f8: N1, --, R4, Q4, K2.
• h6: N2, B2, R3, Q5, --.
• b3: --, B2, R3, Q5, --.
• f3: --, B1, R4, Q4, K2.

The most "impressive" number here, perhaps, is for Qc7. But note that we expect to see bigger figures here for pieces that attack more squares. Perhaps we should think of these numbers as being scaled down by the number of squares attackable by each piece -- after all, we should expect to have seen more things that a Q might be attacking than things that a N might be attacking. Let's do that, rather crudely, dividing each number by the number of squares that would be attacked by the relevant piece on that square. These numbers are all < 1; I'll represent them by percentages, rounding in whatever way seems appropriate. What I'm doing here is a super-crappy approximation to a probabilistic update on the information I've got.

• c7: N17, B57, R21, Q30, K38.
• f8: N25, ---, R29, Q33, K40.
• h6: N50, B29, R21, Q24, ---.
• b3: ---, B22, R21, Q22, ---.
• f3: ---, B09, R29, Q16, K25.

So now the clear outlier is for Bc7. I bet that's where the bishop is. (Spoiler: it is, in both of the configurations that are still possible.)

Well, supposing the B is on c7, what other information do we have?

• 2 of RQKf8, Nh6, Qb3, RQf3
• 1 of RQf8, Qh6, (--), RQKf3
• 1 of (--), RQh6, RQb3, (--)
• 1 of Nf8, RQh6, Qb3, (--)
• 1 of (--), (--), RQb3, Qf3

That's a lot of votes for Qb3, even given that the Q attacks a lot of squares. (Spoiler: one of the two possible configurations has Qb3, the other doesn't.) Suppose we have Bc7 and Qb3; what else do we know?

• 1 of RKf8, Nh6, Rf3
• 1 of Rf8, (--), RKf3
• 0 of (--), Rh6, (--)
• 0 of Nf8, Rh6, (--)
• 0 of (--), (--), (--)

So we are confident that f8 is K or R since it can't be the N. If Rf8 then f3 isn't the K so must be the N, and then Kh6 by elimination. (This is in fact the correct configuration.) On the other hand, if Kf8 then f3 isn't the R so again must be the N, and then Kh6 by elimination... but then the second line here is wrong. So, if our guesses of Bc7 and Qb3 are right, we must have Rf8, Nf3, Kh6. (Again: this is in fact the correct configuration.)

What should we do at this point? I'd be inclined to think: I'm actually pretty confident about Bc7, but not so sure about Qb3 and everything else seems to follow from that. So next question: do we have Qb3? The answer is yes. Maybe we can actually prove Bc7 now without an impossible amount of searching? I mean, even brute force is kinda feasible now; there are only 24 configurations with Qb3. But let's repeat our summary of what we know, taking into account Qb3:

• 1 of Rc7, RKf8, Nh6, Rf3
• 2 of Bc7, Rf8, Bh6, (--), RKf3
• 1 of BKc7, (--), Rh6, (--)
• 0 of Nc7, Nf8, Rh6, (--)
• 0 of RKc7, (--), (--), Bf3

Ha. Look at those last two lines: c7 can't be any of NRK, so we must have Bc7, and our previous analysis tells us all the rest.

So, we ended up using five A-questions and one B-question, after which we were able to identify the correct configuration with certainty; we didn't have to do any very exhaustive searching. I feel like we got a little bit lucky. (I didn't consciously choose any of the questions on the basis of knowing where the pieces actually are.)

Answer 2

This is a question about puzzles, so it's not inherently off-topic for the site. But there's not much of a meaningful answer we can give to some of these questions.

1. According to what strategies could one ask the two types of questions?

2. Where to begin? Does it make sense to ask Questions A first for squares on the rim, as opposed to central squares which are more likely to be seen by a greater number of pieces? Just an idea, maybe retrograde type methods can also be applicable here.

These two questions seem to be pretty similar - there are a number of ways you could approach it.

The mathematically optimal way, if you were a perfect logician with infinite memory and calculation time, is to treat the game as playing against an adversary - instead of there being a hidden configuration at the start, they can answer anything they want as long as there is at least one thing they could have picked. In this version, you win once you narrow it down to only one option. Then, you can just draw out the whole game tree, at every possible state all of the possible configurations. You then figure out what the opponent's best move is at each point, and choose your moves so that you make their best move as bad as possible. (This is called the minimax decision rule, and it works for any finite game. This game is necessarily finite if you never ask a question more than once.)

Of course, this is muddied if you don't happen to have infinite memory and calculation time. In that case, you may prefer questions that lead to quicker positions, or that eliminate certain "sections" of the configuration space. But that's largely dependent on the specifics of your memory and your opponent's patience.

Retrograde methods don't make sense at all, because the pieces are placed randomly - there's not a game being played to lead up to this point. Retrograde analysis is a way of figuring out past positions based on what is illegal - for example, if the king is currently being attacked, you know it is now that player's turn, the other player must have just made a move that caused that. This puzzle does not involve any movement of pieces, so retrograde analysis is entirely irrelevant.

3. Are there analogies, from mathematics, physics or other puzzles, that one could use to formulate the puzzle differently?

Not really? The movements of chess pieces are very specific - I don't see why there would be a nice mathematical or physical analogy here. There are similar puzzles in the genre of "figure out the positions of objects, based on outside 'probes' of some sort" - Black Box, Kin-Kon-Kan, and Battleships come to mind, and you could say that any grid-deduction genre fits that definition. But this puzzle is heavily dependent on the specific movement rules of chess pieces, so there's not going to be a nice alternate representation.