3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You cannot solve Sudoku with a simple neural net..I am not sure but probably it's a combinatorial game..It requires more $\endgroup$ – DuttaA Jun 27 '18 at 10:59
  • $\begingroup$ I know, I'm not trying to actually solve it but just play around a little. My expectation is that there is a neural net that gets pretty close to a solution. But, on the contrary, my trained neural net seems to diverge from the actual solution and I'm trying to find an explanation for that. $\endgroup$ – Felix Gehring Jun 27 '18 at 11:27
  • $\begingroup$ Neural Nets are way overrated...in sudoku i guess you show a few inputs and predict all the other boxes correct? This is a partially revealed state (forgot the exact term) ..I do not think neural nets are good at handlng those $\endgroup$ – DuttaA Jun 27 '18 at 11:29
  • $\begingroup$ Welcome to SE:AI! Glad you found the answer, and hope to see you back soon! (Not strictly related, but if interested in Sudoku decision-making, you might want to check out m,n,p-games, a form of partisan Sudoku. Here's a link to some visual references for the new mechanics: mbranegame.com/tutorial) $\endgroup$ – DukeZhou Jun 27 '18 at 18:35
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Phew, thank you so much. This is way more information than what I hoped for. Now I kind of see how my assumptions were not right in the first place, plus I have lots of new things to read about and try out. $\endgroup$ – Felix Gehring Jun 27 '18 at 18:23
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.