LLMs are also good at connecting the dots and figuring out patterns in a program. For this case it's ok if they miss even 99% of the times, because you can formally verify which solution is correct, and checking a 100 solutions is orders of magnitude faster than checking millions/billions/trillions of possibilities that a traditional solver needs to check.