[zzlk]

a) determine in bounded time whether any solution exists at all

I can't prove it but I think this is roughly the same thing as the circuit satisfiability problem, which is np-complete. So, I think the best thing you can do there is a very large exponential time bound.

b) use a deterministic procedure to find a solution

You can solve this problem deterministically with depth first search. But I found that to be pretty slow and generate not very aesthetically interesting results most of the time.