This actually isn't too hard to make a solver for. Especially in the single white piece case. I made a solver [0] that can solve level 8 (the hardest single white level) in less than 100 ms. I believe that it can solve every single white puzzle, but I haven't tested it thoroughly.

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...

Nice. I had a similar idea and also wrote a little solver in Rust [1]. I chose the same benchmark puzzle as is in your code, and it solves in ~25 microseconds on my laptop (i7-1165G7).

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

This is really neat. Thank you and @thethirdone for putting in the effort to tackle this! Love these creative takes to add efficiency boosts. You guys make HN awesome.

> 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.

It's even simpler than that. You can randomly generate a valid sequence of moves (i.e move to a3, become knight, move to ..., move to ..., become ..., ...) instead of the initial board state and that guarantees the puzzle is solvable.