Constraint Satisfaction Problems solution through Spiking Neural Networks with improved reliability: the case of Sudoku puzzles

Constraint satisfaction problems (CSPs) are a subset of NP-Complete problems: they belong to the NP (nondeterministic polynomial-time) class, a common example of CSP is the latin square problem in the variant of Sudoku puzzles. A possible method to find a solution is through a neuromorphic approach as shown in. Specifically, a stochastic version of a Spiking Neural Network (SNN) made of Leaky Integrate-and-Fire (LIF) neurons and with a structure defined over the mathematical formulation of the CSP can be employed. Such a network describes a system that stochastically evolves towards the solution of the Sudoku puzzle, following the attractor dynamics, in the configuration space. Despite showing the capability of solving this and other CSP problems, presents some limitations that should be addressed: (i) each solution attempt requires a pre-set simulation time that cannot be modified once started, thus hindering the possibility of stopping the process once the solution has been found and introducing unnecessary energy consumption; (ii) the validation method is carried out through the binning process, which consists in extracting the spikes from the neuromorphic platform and analyzing its state through an external platform which inherently implies additional energy consumption due to data preparation and transfer; (iii) the original problem through a mapping process is encoded in the SNN network, given the complexity of some problem classes there may be limitations on the reliability of the network in modeling the initial addresses, observing a modification of these elements during the simulation. Here we propose a fully spiking pipeline able to find a solution, validate it and stop the generation of spikes.