Not really an answer to your question, but is the problem really NP-complete, or just combinatorially difficult? For example how is this condition of NP-completeness satisfied?
> it is a problem for which the correctness of each solution can be verified quickly [0]