Given a board position, there are programs that try to find a series of legal moves that lead to it.
Are there algorithms that can do the opposite - prove that the position is not reachable by a series of legal moves?
Proof by exhaustion doesn't seem possible in the general case due to the size of the search space, but are there other methods?
Easy illegality is easy: not exactly 1 king on both sides, both kings in check, pawns on the final ranks. It's also fairly easy to tally promoted material and subtract the missing pawns. A quick captures test, together with the pawn structures, is also possible.
An impossibility of last move test, even if only cursorily, is already tricky.
A full test is NP-hard (in whatever sense), I fear. There are many chess problems asking "Legal?" and they can be fiendlishly hard. (Note that the mentioned programs have no chance against them.) In any case, a quick illegality test is far easier than a quick legality test, if the position looks even remotely doubtful.
The only way to decide, apart from obvious cases, is to use backtracking. In doing so, you are basically exhaustively checking each possible move and making a series of moves that would lead to that position. This is no less complex than going forward. Actually, including en passant, promotion, castling, not castling, and capturing a possible piece at any given position it is even more complicated. (Not much of an algorithm, it is just brute force which is the name of the actual algorithm.)
The reason it is more complicated than analyzing possible positions is that some of the positions done in reverse may actually be impossible themselves. But then, it is sufficient to find only one possible chain of moves to claim that a position is possible. The rest of the analysis is more or less wasted.
At the moment we have the 7-piece end game library and we are trying to create the 8-piece library and that will be very likely it. As you can see, even if we reach a 10-piece end game library that is not enough to cover all regular situations let alone irregular ones.
Note that it is a very big problem that you ask only about possible positions, disregarding the fact that people might never play and reach those positions. That is simply throwing away all heuristics that we have, which are designed for regular play style, where you want to win.
I would argue that in general way too many reachable positions are possible, but all totally unrealistic. So instead of going backward for each such position I would probably still go forward simply ignoring all the rules about winning or losing and just trying to arrange figures to get to that position.
This analysis might actually reveal that only some set of positions are impossible, regarding for example pawn structure, but the remaining figures as long as there are no two white bishops etc. are much more flexible. This is basically so, because by disregarding pawn structure you could revert each figure to its initial position first and then if this is so for all positions, only then think about if it is possible that all other missing figures are taken by your opponent.
If I am right, it would leave only pawn structure as the one that defines if a position is possible (even if stupid) or not.
That would leave then to analyze still quite some number of pawn arrangements. But I would definitely start from there.
Anyway I would definitely try to, regardless of artificiality, return each figure to its original position first. This is because it is very easy to offer a figure to the opponent and not ruin the initial structure, you just move the figure until it gets close to whatever it can take and there you are.
This generic approach might actually work in quite some number of cases. But... it is still heuristic and it would require quite some effort to prove that it might be working in general.
Not to leave the story empty handed
The total number of ways figures can be arranged around a table
13^64
since we have 6 different black and 6 different white pieces and one is for an empty space (as you can see I deliberately do not call this a position rather just an arrangement)
About the number of sensible positions and the number of sensible games, they differ only by a small factor because the branching factor is small. (Suppose we start from one possible position and have 2 different moves to choose from. After 8 moves we would have 2^8=256 possible games, if they do not overlap, and 1+2+4+8+16+32+64=127 possible positions. In chess the branching is about 3.) So we can say that the number of sensible positions is about the same as the number of sensible positions estimated to 10^40.
So the probability that a totally random position you set is sensible one as well is roughly 10^-30, or should I say it is close to impossible of doing it randomly.
One thing that would be quite interesting to know is how many groups of connected positions legal or illegal we have in chess. Connected means that you can reach one position from another. Nobody cares about these things, but we are not going to resolve chess in mathematical sense if we do not start asking these questions.
