How can a neural network learn to play sudoku?
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.