Class encapsulating the network for solving Sudoku


Run this example as a Jupyter notebook:

See our guide for more information and troubleshooting.


The class SudokuNet constructs a network of LIF neurons with static synapses that due to their connectivity rules can converge on valid solutions for Sudoku.

Notes

The functionality of the network lies entirely within the inhibitory connections between neuron populations. Each population of size n_digit encodes a digit between 1 and 9 in one of the 81 cells and has outgoing inhibitory connections to several other populations. Namely all populations coding for the same digit in the same row, column and 3x3 box of the sudoku field, since a given digit can only ever occur once in any of those three. It also inhibits all populations in the same cell which encode different digits to force the network to converge on a single digit per cell.

If the network is simulated with just this configuration and some background noise, it converges naturally on states that represent valid solutions for Sudoku.

If populations coding for specific digits in some of the cells are stimulated externally (therefore inhibiting all other digits in the same cell), the network usually converges on a solution compatible with the input configuration, thus solving the puzzle.

Authors:

J Gille, S Furber, A Rowley

import logging

import nest
import numpy as np

inter_neuron_weight = -0.2  # inhibitory weight for synapses between neurons
weight_stim = 1.3  # weight from stimulation sources to neurons
weight_noise = 1.6  # weight for the background poisson generator
delay = 1.0  # delay for all synapses

neuron_params = {
    "C_m": 0.25,  # nF    membrane capacitance
    "I_e": 0.5,  # nA    bias current
    "tau_m": 20.0,  # ms    membrane time constant
    "t_ref": 2.0,  # ms    refractory period
    "tau_syn_ex": 5.0,  # ms    excitatory synapse time constant
    "tau_syn_in": 5.0,  # ms    inhibitory synapse time constant
    "V_reset": -70.0,  # mV    reset membrane potential
    "E_L": -65.0,  # mV    resting membrane potential
    "V_th": -50.0,  # mV    firing threshold voltage
    "V_m": nest.random.uniform(min=-65, max=-55),
}


class SudokuNet:
    # number of neuron populations (rows*columns*digits)
    n_populations = 9**3

    def __init__(self, pop_size=5, noise_rate=350.0, stim_rate=200.0, input=None):
        self.stim_rate = stim_rate  # frequency for input generators
        self.pop_size = pop_size  # number of neurons per population
        # total number of neurons
        self.n_total = self.n_populations * self.pop_size

        logging.info("Creating neuron populations...")
        self.neurons = nest.Create("iaf_psc_exp", self.n_total, params=neuron_params)

        logging.info("Setting up noise...")
        self.noise = nest.Create("poisson_generator", 1, {"rate": noise_rate})
        nest.Connect(
            self.noise,
            self.neurons,
            "all_to_all",
            {"synapse_model": "static_synapse", "delay": delay, "weight": weight_noise},
        )

        # one stimulation source for every digit in every cell
        self.stim = nest.Create("poisson_generator", self.n_populations, {"rate": self.stim_rate})

        # one spike recorder for every digit in every cell
        self.spikerecorders = nest.Create("spike_recorder", self.n_populations)

        # Matrix that stores indices of all neurons in a structured way
        # for easy access during connection setup.
        # Dimensions: (row, column, digit value, individual neuron)
        self.neuron_indices = np.reshape(np.arange(self.n_total), (9, 9, 9, self.pop_size))

        # Matrix that stores indices of inputs and outputs of the network
        # (stimulation sources and spike recorders) to be connected to the
        # neurons. Dimensions: (row, column, digit value)
        self.io_indices = np.reshape(np.arange(self.n_populations), (9, 9, 9))

        logging.info("Creating inter-neuron and IO-connections...")
        for row in range(9):
            # First and last row of the current 3x3 box.
            box_row_start = (row // 3) * 3
            box_row_end = box_row_start + 3

            for column in range(9):
                # First and last column of the current 3x3 box.
                box_col_start = (column // 3) * 3
                box_col_end = box_col_start + 3

                # Obtain all populations in the surrounding 3x3 box.
                current_box = self.neuron_indices[box_row_start:box_row_end, box_col_start:box_col_end]

                for digit in range(9):
                    # population coding for the current row, column and digit
                    sources = self.neuron_indices[row, column, digit]

                    # populations in the same row coding for the same digit
                    row_targets = self.neuron_indices[row, :, digit]
                    # same as above for the current column
                    col_targets = self.neuron_indices[:, column, digit]
                    # populations coding for the same digit in the current box
                    box_targets = current_box[:, :, digit]
                    # neurons coding for different digits in the current cell
                    digit_targets = self.neuron_indices[row, column, :]

                    targets = np.concatenate((row_targets, col_targets, box_targets, digit_targets), axis=None)
                    # Remove duplicates to avoid multapses
                    targets = np.unique(targets)
                    # Remove the sources from the targets to avoid the
                    # population inhibiting itself.
                    targets = np.setdiff1d(targets, sources)

                    # Transform indices into NodeCollections
                    sources = self.neurons[sources]
                    targets = self.neurons[targets]

                    # Create inhibitory connections
                    nest.Connect(
                        sources,
                        targets,
                        "all_to_all",
                        {"synapse_model": "static_synapse", "delay": delay, "weight": inter_neuron_weight},
                    )

                    # connect the stimulation source to the current population.
                    # Weights are initialized to 0 and altered in
                    # set_input_config()
                    nest.Connect(
                        self.stim[self.io_indices[row, column, digit]],
                        sources,
                        "all_to_all",
                        {"delay": delay, "weight": 0.0},
                    )

                    # connect current population to a single spike_recorder
                    nest.Connect(sources, self.spikerecorders[self.io_indices[row, column, digit]])

        if input is not None:
            logging.info("setting input...")
            self.set_input_config(input)

        logging.info("Setup complete.")

    def reset_input(self):
        """Sets all weights between input and network neurons to 0."""
        nest.GetConnections(self.stim).set({"weight": 0.0})

    def set_input_config(self, input):
        """Sets the connection weights from stimulation sources to populations
        in order to stimulate the network according to a puzzle configuration.

        Parameters
        ----------
        input : np.array
            a np.array of shape (9,9) where each entry is the value of the corresponding
            cell in the sudoku field. Zero-valued entries are ignored.
        """
        self.reset_input()

        for row in range(9):
            for column in range(9):
                value = input[row, column]

                # only apply stimulation where the input configuration dictates a number
                if value != 0:
                    connections = nest.GetConnections(self.stim[self.io_indices[row, column, value - 1]])
                    connections.set({"weight": weight_stim})

    def get_spike_trains(self):
        """Returns all events recorded by the spike recorders.

        Returns:
            np.array
                array of all the data from all spike recorders
        """
        return np.array(self.spikerecorders.get("events"))

    def reset(self):
        """Resets the network in three steps:
        setting all input weights to 0
        resetting all membrane potentials to their default value
        deleting all recorded spikes
        """
        self.reset_input()
        self.reset_V_m()
        self.reset_spike_recorders()

    def reset_V_m(self):
        """Resets membrane potential of all neurons to (uniformly random) default values."""
        self.neurons.V_m = nest.random.uniform(-65, 55)

    def reset_spike_recorders(self):
        """Deletes all recorded spikes from the spike recorders connected to the network."""
        self.spikerecorders.n_events = 0

    def set_noise_rate(self, rate):
        """Sets the rate of the Poisson generator that feeds noise into the network.

        Parameters
        ----------
        rate : float
            average spike frequency in Hz
        """
        self.noise.rate = rate

Total running time of the script: ( 0 minutes 0.000 seconds)

Gallery generated by Sphinx-Gallery