The ChessPositionRanking project, with help from the Texel chess engine author, tries to prove random positions (that are not obviously illegal) legal by constructing a game ending in the position. If that fails it tries to prove the position illegal. This now works for over 99.99% of randomly generated positions, so one can feed the legal game record found for random legal positions.