This is one of the magical spaces where there is always a solution, the board space isn't that big & shrinks as you go
It works by reducing the state to currently alive pieces and the current white piece right after conversion. It computes the transversable squares and possible captures for each state and does a basic DFS. One neat trick I used is that for simple traversability, the queen and the king are the same piece.
Multiple white pieces makes the code significantly more complex, but it simply adds a little bit to the statespace.
[0]: https://github.com/TheThirdOne/assorted-examples/blob/master...
I haven't optimized my approach at all or even run it under a profiler, but it uses SIMD-within-a-register for computing the "flood fill" of which squares a piece can move to, which is a nice efficiency boost. For the simplest example, if you have a bit-vector `v: u64` of positions that a pawn might be in, then `v << 8` is the vector that denotes where it might be after one step, and `((v & can_move::LEFT) << 7) | ((v & can_move::RIGHT) << 9)` denotes what it might be able to capture.
I think the `Stepper` implementations and the way they flow into the top-level `captures` function is a cool and powerful approach; I encourage taking a look if it sounds interesting to you.
[1]: https://github.com/wchargin/echo-chess
Direct link to source:
https://github.com/wchargin/echo-chess/blob/main/src/main.rs
> Multiple white pieces makes the code significantly more complex, but it simply adds a little bit to the statespace.
That would be my guess too. Especially the sacrifice mechanic that needs to be timed just right after X moves/transformations of each white piece.