The cost-effective, high-density, and robust floating-gate (FG) spin coupler based on the NOR flash technology is proposed for the first time to overcome the challenges of convergence speed and the capacity limitation in the conventional SRAM-based simulated annealing (SA) machines. In addition, the novel complementary read algorithm can further increase the tolerance on threshold voltage (Vth) variation by 60%. Demonstrations show that the proposed in-memory spin coupling architecture provides high efficiency and scalability in solving the combinatorial problems regardless of the problem size.