Solving constraint satisfaction problems (CSPs) is a notoriously expensive computational task. Recently, it has been proposed that efficient stochastic solvers can be obtained via appropriately configured spiking neural networks performing Markov Chain Monte Carlo (MCMC) sampling. The possibility to run such models on massively parallel, low-power, neuromorphic hardware holds great promise; however, previously proposed networks are based on probabilistic spiking neurons, and thus rely on random number generators or external sources of noise to achieve the necessary stochasticity, leading to significant overhead in the implementation. Here we show how stochasticity can be achieved by implementing deterministic models of integrate and fire neurons using subthreshold analog circuits that are affected by thermal noise. We present an efficient implementation of spike-based CSP solvers implemented on a reconfigurable neural network VLSI device, which exploits the device's intrinsic noise sources. We apply the overall concept to the solution of generic Sudoku problems, and present experimental results obtained from the neuromorphic device generating solutions to the problem at high rates.