Granted, it is harder to solve than to generate a problem.
However, it's also
In addition, unlike cryptographic hash algorithms, small permutations produce predictably related results. From one almost-solution you can find full solutions, etc.
We just need an efficient way to converge to a solution.
I have two ideas to speed up the process.
One is bottom-up and involves a sort of messed-up A-star graph search, where edges are assigned dynamic weights based on their neighbors. Then at each step, we sort the three new directions' weights (say, left=2, down=0 up=-infty) This will allow us to prevent exploring paths where there is already. If all of those paths prove impossible, then we can back up a step. This can be done pretty easily given an array and something like a list or a stack.
It's a small size list (3) so we can use quick comparisons to sort. If we need to look ahead further than 1 step, I have already a basic insertion sort written that I use for diet purposes. To deal efficiently with edged pieces (like the bishop) we can check for those as neighbors and factor that into the dynamic weight. This won't improve our absolute performance much but will improve theoretical performance.
My other idea is related but top-down: use zoning of oxen and knights and pawns to cut down on the edges. There are a limited number of positions and orientations for all of the pieces like knights and oxen, so we can generate them one at a time, test them for collision (with other colors, other zones, or other pieces), assign higher weights to outer edges, assign "impossible" weights to bisecting edges, and if witches are present, generate random eliminations. For each space-map of the board, we can then start gnerating a path.
This starts to get complicated though if you start to account for touching edges and zones that are set up againsy the border.
Assuming Jick isn't deliberately generating puzzles that such an algorithm is weak to, this should help most of the time. I think.