Answers.Body: <p>You can take a look at this <a href="https://arxiv.org/pdf/1905.12149.pdf" rel="nofollow noreferrer">paper</a> that solving your problem with a neural network. You can use the pytorch implementation of the satnet layer : <a href="https://github.com/locuslab/SATNet" rel="nofollow noreferrer">satnet layer API</a>. 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-25T08:40:57.983Z
Answers.LastActivityDate: 2019-10-25T08:40:57.983Z
Answers.UserDisplayName: Adrien Forbu
Answers.Body: <p>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.</p>
  <p>Maybe you could learn something by reading up on it: <a href="https://github.com/nikcheerla/deeplearningschool/deeplearningschool/2018/01/01/AlphaZero-Explained/" rel="nofollow noreferrer">https://github.com/nikcheerla/deeplearningschool/deeplearningschool/2018/01/01/AlphaZero-Explained/</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-21T23:59:43.573Z
Answers.Text: While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference.  Link-only answers can become invalid if the linked page changes. - [From Review](/review/late-answers/23187)
Answers.UserDisplayName: Rob
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-11-21T18:42:14.623Z
Answers.LastActivityDate: 2022-11-21T18:42:14.623Z
Answers.UserDisplayName: Maks
Answers.Body: <p>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. </p>
  
  <p>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.</p>
  
  <p>However, you could apply reinforcement learning techniques to learn an optimal policy to solve sudoku.</p>
  
  <p>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. </p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-06-27T18:23:35.317Z
Answers.Text: 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.
Answers.UserDisplayName: Felix Gehring
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-06-27T13:09:18.030Z
Answers.LastActivityDate: 2019-10-22T20:54:48.223Z
Answers.LastEditDate: 2019-10-22T20:54:48.223Z
Answers.UserDisplayName: thecomplexitytheorist
Body: <p>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.</p>
  
  <p>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.</p>
  
  <p>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:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>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.</p>
  
  <p><strong>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.</strong></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-06-27T11:27:51.273Z
Comments.Text: 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.
Comments.UserDisplayName: Felix Gehring
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-06-27T18:35:10.943Z
Comments.Text: 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](https://www.reddit.com/r/abstractgames/comments/8khl96/formal_definition_of_mnpgames/), a form of partisan Sudoku. Here's a link to some visual references for the new mechanics: http://mbranegame.com/tutorial/)*
Comments.UserDisplayName: DukeZhou
Tags: <neural-networks><machine-learning><game-ai><combinatorial-games><multilayer-perceptrons>
Title: How can a neural network learn to play sudoku?
UserDisplayName: Felix Gehring
ThreadText: # How can a neural network learn to play sudoku?
  
  (Asked by: username_0 on 2018-06-27)
  
  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.**
  
  **Tags:** neural-networks, machine-learning, game-ai, combinatorial-games, multilayer-perceptrons
  
  > **Comments:**
  > **username_0**: 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.  
  > **username_1**: 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](https://www.reddit.com/r/abstractgames/comments/8khl96/formal_definition_of_mnpgames/), a form of partisan Sudoku. Here's a link to some visual references for the new mechanics: http://mbranegame.com/tutorial/)*  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_5 on 2018-06-27. Score: 3 | Accepted answer
  
  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.
  
  > **Comments:**
  > **username_0**: 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.  
  
  ---
  
  ### Answer by username_2 on 2019-10-25. Score: 2
  
  You can take a look at this [paper](https://arxiv.org/pdf/1905.12149.pdf) that solving your problem with a neural network. You can use the pytorch implementation of the satnet layer : [satnet layer API](https://github.com/locuslab/SATNet). 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 by username_3 on 2022-11-21. Score: 0
  
  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/>
  
  > **Comments:**
  > **username_4**: While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference.  Link-only answers can become invalid if the linked page changes. - [From Review](/review/late-answers/23187)  
  
  ---
  
  