Generate tests for a backtrack code

I have a piece of code, let's say a function foo, which uses backtracking to solve a problem. foo finds the minimal number of actions to perform so as to reach a desired state.

Thus, any brute-force try would look more or less the same as my code. Is there any way to generate automatic tests for such a problem?