Recent progress in the development of phase-change materials is enabling their use for novel approaches in spike-based learning circuits and brain-inspired computing architectures , . The race to leverage efficient low-power neural processing systems whose fundamental operations are akin to those of animal brains drives the community to explore new ‘neuromorphic’ materials and devices . Amongst the candidates suitable to deliver such types of devices, vanadium-dioxide (VO 2 ) offers promising features . Its polycrystalline morphology, once integrated on a Si platform, has the ability to oscillate from a high to a low resistive statenear room temperature (68°C) . These natural oscillations triggered by biasing VO 2 at low voltage provide means to build a network of electronic oscillators with tremendous potential for neural network architectures, AI applications, and optimization capabilities , , , . In particular, oscillation-based computing serves best to solve constraint-satisfaction problems , . Any optimization problem, simple in appearance, typically requires heavy computing resources calling for long processing times and even larger energy consumption . In this work, we show the power and the number of cycles needed to reach a solution can be dramatically reduced to solve NP-hard problems with our befitted VO 2 -based 3×3 oscillating neural networks (ONNs).