How does one know if a position is not reachable from a series of legal moves from the starting position?

Question

If one of the following is true, a position is not reachable from the starting position by a series of legal moves:

1. One side has two or more kings or one side has no kings;
2. One side has a total of 10 or more queens and pawns, or a total of 11 or more rooks and pawns, or a total of 11 or more knights and pawns, or a total of 10 or more bishops of the same colour and pawns;
3. One side has a total number of more than 16 pieces;
4. At least one pawn is in the first rank or eighth rank;
5. Both kings are being checked;
6. The kings can capture each other in the next move;
7. At least one bishop is in an "impossible square" blocked by pawns in their starting positions, such as the following:

8. One king is being "impossibly" checked or checkmated such as the following (this should also include the case where a king is being checked by three or more pieces): (I am not sure how to define this more precisely);

9. One side is checking and it is his turn.

I am sure that this list is not exhaustive. Does one know a complete list? Is there an algorithm determing whether a position is reachable from the starting position by a series of legal moves?

Edit: I would also add the following:

• One side has more than 8 pawns.

Answer 1

Here is a retro which needs deep analysis:

[Title "Thierry le Gleuher; Economy Records in Add Unit(s) Problems, 5A"]
[StartFlipped "0"]
[fen "B5bn/5PrR/5prN/6pk/7p/5P2/PPPPPP2/KR1Q2N1 w KQkq - 0 1"]

The stipulation is "Add the missing unit(s)". A solution may be found in entry P1227636 in PDB. In brief:

To disentangle Black's kingside, White must retract most pieces back home so that White can retract g2xf3. Interleaved with these White moves are 19 Black moves. But, all this time, Black has no retrotempi with units in the diagram, so they must be provided by the added units. The only way is to add black pawns on a3, b3, c3, d3, e3. Each provides 4 retrotempi, except that the b and d pawns can't both retract home, because the bishop on g8 will need to retract to c8 eventually.

Thus the position would be illegal if

5 black pawns were added but any of them were nearer rank 7, because Black would run out of retrotempi, but it would take deep analysis to show that this is the case.

This might be the sort of situation RemcoGerlich was thinking of, seeing that

Some White pieces need to leave the back rank and move back in a different order.

In case you thought that there's a simpler way to add units:

A Black piece captured White's c1 bishop on c1. White is not missing anything else, so no Black pawn ever left its file. Thus White's 3 captures g2xf3 and hxgxf were of Black's 3 missing pieces: the f8 bishop, the queen and a knight. So we may add Black pawns but not a piece.

Answer 2

This is part of a whole genre of chess problem, retrograde analysis. People keep coming up with new tricks in positions that make it impossible to reach them, possibly in surprising ways.

I'm copying a diagram here from the question Searching for a "where is the black king" puzzle?:

8/8/8/1r1b4/B7/8/8/3k4 w - - 0 1

Problem: place a white king on the board to make the position legal

Spoiler:

It's on c3. The reasoning is that it's black to move, so white's king can't be on b3 as it would be in check. So black is in check by the Ba4. But then the king must have just left b3, and it was in double check there. But how can it be in double check by a rook on b5 and a bishop on d5? Only by an en passant capture. There was a black pawn on b4, a white pawn on c2, and the last moves were 1.c2-c4 b4xc3e.p.++ 2.Kb3xc3.

This means that the position with the white king placed on that square is reachable, but with the king anywhere else it's unreachable. That's not easy to spot just by checking items from a list!

That's an easy retrograde analysis problem. Some of them need quite deep analysis, like several pieces have left the bottom rank, they could each have left it over some square, but only in the order they're in on the back row, and they must have left in some other order -- but I can't find a problem like that now.

I believe your list can be made arbitrarily long.

As for algorithms, there are better ways than the brute force approach I described in my comment on the question: there has been work on finding proof games in retrograde analysis. These take it a step further: they find a game that reaches the given position in a set number of moves. That should also be enough to find whether the position can be reached at all.

I found the software Natch that can do this.

Answer 3

First of all, if you can't find a way to reach a position from an opening board, then it's likely illegal. I say likely only because you may have missed something.

Here is a fairly nice collection of illegal positions that I ran across a while ago on a chess.com forum. Some of the positions are extremely subtle. One common theme I noticed that isn't on your list is doubled pawns when there cannot be doubled pawns (for example, doubled pawns with no pieces captured, doubled pawns on the 2nd and third rows when the only piece of the opponent's captured is a bishop of the color of the unmoved pawn on the second row, etc, etc.)

Another one is impossible move order - something that usually happens with knights. For example, it is impossible for it to be black's turn with all of the pieces in their starting position - this is because of the white-black, white-black, white-black pattern of the knight's moves.

There are many more good examples, I'm sure. If anyone thinks of any, leave a comment and I'll add it in!

It is probable that neither our posts nor the link I gave will ever provide a comprehensive list of all the categories of illegal positions, but again - if it can't be reached from the beginning of the game, it's illegal.