How to detect an illegal position?

Question

There are many positions in chess that are illegal in the sense that they cannot be reached by legal moves.

Is there an algorithm to detect if a position is illegal or not?

Answer 1

Not really, or, at least, nothing that is of practical value.

You could, in theory, play the game backwards. If no branch reaches the initial position you have shown it is 'illegal'. This is mainly a chess problem area: for more info see https://en.wikipedia.org/wiki/Proof_game. There is also software for proof games, but, as all software, limited (see https://en.wikipedia.org/wiki/Software_for_handling_chess_problems).

The problem area of retroanalysis (which typically only regards less specific questions than full proof games) touches on your question. (See https://en.wikipedia.org/wiki/Retrograde_analysis), and some of the ideas from that field can be used to identify some illegal positions, but can't necessarily cover all of them.

So: no algorithm for illegal positions. For legal positions an algorithm can be formulated (see proof games above), but can't necessarily be implemented to perform in a period of time that is practical for humans.

A closely related question was asked in: Are there any illegal positions that are difficult to spot? and many of the example positions may add further light.

Answer 2

Well, you could generate all possible positions, and draw arrows between two positions A and B, if B can be reached from A in a single move.

Then use Dijkstra to see whether there is a finite-length path between the starting position, and the position you want to determine whether it is illegal or not.

But that's just a theoretical exercise. The shear amount of possible positions makes this unfeasible to use this in practice.