How can a neural network learn to play sudoku?

Question

I'm just beginning to understand neural networks and I've performed a couple of successful tests with numerical series where the NN was trained to find the odd one or a missing value. It all works pretty well.

The next test I wanted to perform was to approxmimate the solution of a Sudoku which, I thought could also be seen as a special kind of numerical series. However, the results are really confusing.

I'm using an MLP with 81 neurons in each of the three layers. All output neurons show a strong tendency to yield values that are close to either 0 or 1. I have scaled and truncated the output values. The result can be seen below:

Expected/Actual Solution:     Neural Net's Solution:

6 2 7 3 5 0 8 4 1             9 0 9 9 9 3 0 0 3
3 4 8 2 1 6 0 5 7             0 9 9 0 0 0 9 9 0
5 1 0 4 7 8 6 2 3             0 9 1 9 9 0 2 0 4
1 6 4 0 2 7 5 3 8             0 0 5 0 0 9 0 0 7
2 0 3 8 4 5 1 7 6             0 0 0 0 0 9 9 0 9
7 8 5 1 6 3 4 0 2             9 9 9 9 0 6 2 9 0
0 5 6 7 3 1 2 8 4             0 0 0 0 9 9 0 9 0
4 3 1 5 8 2 7 6 0             9 9 0 0 0 0 9 0 9
8 7 2 6 0 4 3 1 5             9 9 0 9 9 0 9 0 9

The training set size is 100000 Sudokus while the learning rate is a constant 0.5. I'm using NodeJS/Javascript with the Synaptic library.

I don't expect a perfect solution from you guys, but rather a hint if that kind of behavior is a typical symptom for a known problem, like too few/many neurons, small training set, etc.

Answer 1

I think it is the wrong way to frame sudoku as a regression problem in neural networks. Firstly, you have to understand what regression is. "Regression" is when you predict a value given certain parameters, where the parameters are related to the value you have to predict. This happens because at the core neural networks are "function approximators", they model the function by adjusting their weights using lots of data. They tend to form a highly non-linear boundary to separate classes internally in a high dimensional data-space.

The sudoku doesn't fit in this scenario, the combinatorial complexity of sudoku is way too high for a neural network even if you add many layers to it, it is a totally different problem in its own right. You simple can't "regress" the right values of a perfect sudoku here, they are not numbers like "pixel " intensities in images.

However, you could apply reinforcement learning techniques to learn an optimal policy to solve sudoku.

And you have mentioned an "approximate" solution for the sudoku, what do you mean by "approximate"? If you mean by this that only a few squares are out of place, then it is a wrong assumption, because neural networks are proven to be good image classifiers, as they are robust to translational invariance in this case, that is not what you need.

You could, however, do a small experiment to see what the neural network actually learns, replace the numbers by pixel value intensities and train a generative adversarial network on the sudoku images and see the images of sudokus produced by it, to see what actually the network can't learn.

Answer 2

You can take a look at this paper that solving your problem with a neural network. You can use the pytorch implementation of the satnet layer : satnet layer API. In this supervised setup the layer also learn the boolean constraints of your model. You can find an example of a sodoku solver in the github repo.

Answer 3

I think DeemMind’s AlphaZero could provide an answer. Meaning, like others have said solving Sudoku is not a regression or classification problem. The net needs to learn the rules then implement them, just like in chess.

Maybe you could learn something by reading up on it: https://github.com/nikcheerla/deeplearningschool/deeplearningschool/2018/01/01/AlphaZero-Explained/