Indeed, I suspect the approaches/algorithms for solving a Rubik's cube "compress" a lot better than trying to distill the entire search space in order to be able to predict the exact next move.

I see this trope fairly often, i.e. the assumption that an LLM would need to have been trained on <exact thing it is being asked to solve>. Now, while I do have a moderate amount of background in AI, I am definitely not an expert on LLMs as such. I would be interested to hear someone's take, who does work actively in LLM research. Can they generalise "well enough"? They certainly seem to be able to do so, from my anecdata, and I don't believe "training explicitly for every possible scenario" would have scaled even to today's state.