This looks like the same post as the one at the end of the previous thread. So I'll respond just here.

1. An immediate concern is that this is no a planning problem like wolf-goat-cabbage. It's essentially the same as SEND+MORE=MONEY. It's not planning because it doesn't require the system to generate a sequence of steps that will take it from an initial state to a final state.  That is, the output from the system is not a sequence of steps., which is what defines a planning problem.

2. If you solve a problem of one sort, you should be able to solve other similar problems using the same model.  That's not a matter of solving multiple problems; it's a matter of using a single model to solve different instances of a single problem type. So it counts as only one problem, not as a problem for each example instance. 

3. That's why a fixed complexity constant doesn't work. A larger version of the same problem type is not more complex if the same model can handle it. Yet a larger version of the same problem type will require more brute force trials than a smaller one. So a fixed number of brute force trials doesn't capture very much. What matters in complexity is the function that characterizes how fast the number of brute force trials grows as a function of the size of the problem. If the problem is of size n, do you in the worst-case need n*2, 2^n, n^n, etc. brute force trials to get to the solution? In any event, I suggested thinking in complexity-like terms as a way to get started on estimating the difficulty of a problem. I don't have a formal measure of problem difficulty. Use your best judgment.