In single-step Q learning, you can use almost any exploration policy that you like, provided it covers all choices eventually. Usually you want to focus around the target policy, because that is the most likely to visit parts of the trajectory (state, action, reward sequences) that you want to explore for improvements.
The main problem with using a softmax policy in Q learning* is that you have no independent set of preferences, just value estimates. So the agent's exploration performance would become dependent on the scaling of the reward signals. A simple method to adjust for that is to use a temperature hyperparameter $T$, that divides the action value estimates used in the softmax. A high temperature results in near random behaviour, and a low one will almost always select actions with the highest action value. You can start with a high temperature and slowly decay it, similar to decaying $\epsilon$ for $\epsilon$-greedy.
Will this help for you case? Maybe . . . although using an approach which filtered out the impossible actions would be cleaner and definitely faster (in terms of number of samples required).
There are other approaches you could use, such as Thompson sampling, Gibbs sampling, upper confidence bound (UCB). Some of these don't translate easily to deep RL, so you don't see them mentioned as often, but they can work nicely in tabular approaches.
* Outside of Q-learning, in policy gradient and actor-critic methods a softmax policy can be used more directly, and might be a good choice when action space is large.