This paper discusses circuits and architecture of stochastic nanomagnets to efficiently solve NP-complete Boolean satisfiability problems which do not have a known algorithm that can run on classical hardware to solve the problem with a provable guarantee efficiently. The proposed scheme exploits a straintronic interaction of coupled nanomagnets where the neighboring stochastic magnets can be programmable anti-correlated. Using this interaction, a simulated annealing-based accelerator is presented where the constraints of the satisfiability problem can be relaxed at the beginning for an efficient and swift search across its Boolean space. As the accelerator converges to the optimal solution, problem constraints can be gradually imposed by programming the piezoelectric coupling of magnets.