Different sets of moves can lead to the same state, so if you can cache that a given state will not lead to a solution you can stop exploring that branch when you encounter it again.
Is that 'dynamic programming' or is that just keeping a set of explored states?