Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Can Neural Networks Crack Sudoku?

github.com

Post reply on HN
Print view View original

31–40 of 111 posts

Re: Can Neural Networks Crack Sudoku?

#31

Post by timdellinger »

To me, this answers the question "How well can neural networks crack sudoku if we forget all of our domain knowledge, and just try to brute force our way through with insufficient training data and a neural network that's poorly sized?".

I suggest an alternate approach that would use a training set consisting of real-world data of sudoku puzzles that are in the process of being solved: before a box is filled in, and then after it's filled in. This would teach the network to solve the puzzle one step at a time, instead of all at once.

If you insist on only using the as-received puzzle and the solution for training, my intuition is that you'll need more layers than 10 in the NN, and much much more data.

A taxonomy of what complex solving strategies need to be learned already exists: see e.g. http://www.sudokuwiki.org/y_wing_strategy and the categories "basic", "tough", diabolical", and "extreme". My guess is that the NN (using the original author's strategy, but with more layers and lots more data) will eventually do well on "basic" and "tough", but will start to miss on some of the latter conditions depending on the training set and how the network is set up.

Re: Can Neural Networks Crack Sudoku?

#32

Post by dahart »

bhaavan wrote: post #26
trextrex wrote: post #21

That looks interesting. Sudoku is a fairly useful constraint satisfaction problem/testbed to test neural networks architectures on, since the most general version of sudoku is NP-complete. There was some interesting work a while ago that solved sudoku using spiking neural networks too [1] (Fig. 5) with some nice associated theory. [1] http://journals.plos.org/ploscompbiol/article?id=10.1371/jou...

I thought Sudoku can be solved in constant time. It would be a O(9! * 9! ) or something, which is just a O(1), isn't it?

A constant time solution in years or eons isn't very helpful. There are around 6.7e21 complete sudoku boards if you want to brute force enumerate them.

https://en.m.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumer...

Re: Can Neural Networks Crack Sudoku?

#33

Post by CJefferson »

likelynew wrote: post #16
brian_herman wrote: post #3

You can solve sudoku with a SAT solver. You don't need neural networks, this was an assignment in cs 251 at UIC.

There are no easy way to solve SAT as the size of sudoku. Modern day SAT solvers are very large and contains years of experience, containing 10s of heuristics and complex structures. If we can simplify using neural network, I think it's a great step.

Reasonably modern SAT solvers (Say MiniSAT) have a lot less complexity than a modern neural network.

Also, I set as a intro to C practical writing a SAT solver which can easily solve any real-world Sudoku instance.

Re: Can Neural Networks Crack Sudoku?

#34

Post by CJefferson »

sarabande wrote: post #5

I find it interesting that when the NN fails to complete the whole puzzle, it seems to fail spectacularly (github.com/Kyubyong/sudoku#results) -- that is, there aren't a lot of good-partial attempts (90% or above). Does anyone know why this might be the case? Does the first wrong placement of a number in a gap essentially ruin the rest of the guesses?

One big problem is the network is never trained on incorrect Sudokus, so at that point it's effectively into random guessing.

Re: Can Neural Networks Crack Sudoku?

#36

Post by tom_mellior »

dahart wrote: post #32
bhaavan wrote: post #26

Earlier quoted context omitted.

I thought Sudoku can be solved in constant time. It would be a O(9! * 9! ) or something, which is just a O(1), isn't it?

A constant time solution in years or eons isn't very helpful. There are around 6.7e21 complete sudoku boards if you want to brute force enumerate them. https://en.m.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumer...

> if you want to brute force enumerate them

But you don't. Even what you might call "brute force" Sudoku solvers start from the given hints in the puzzle, which reduce the search space considerably. Given a set of Sudoku hints with a unique solution, you won't need "years or eons" with even a very simple solver.

Re: Can Neural Networks Crack Sudoku?

#37

Post by LanceH »

sarabande wrote: post #5

I find it interesting that when the NN fails to complete the whole puzzle, it seems to fail spectacularly (github.com/Kyubyong/sudoku#results) -- that is, there aren't a lot of good-partial attempts (90% or above). Does anyone know why this might be the case? Does the first wrong placement of a number in a gap essentially ruin the rest of the guesses?

Once you get a few right, the solution spaces closes very fast. A valid sudoku puzzle has a unique solution, so if you had 90% correct, there would only be one thing to choose from for each of the other 9 spaces.

Re: Can Neural Networks Crack Sudoku?

#39

Post by DrNuke »

One underlying question is who pays for diffuse crowdsourcing in 2017? I have indirect notice of at least a dozen small enterprises suspected of raiding githubs daily and refactorizing for commercial purposes.

Re: Can Neural Networks Crack Sudoku?

#40

Post by dahart »

tom_mellior wrote: post #36
dahart wrote: post #32

Earlier quoted context omitted.

A constant time solution in years or eons isn't very helpful. There are around 6.7e21 complete sudoku boards if you want to brute force enumerate them. https://en.m.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumer...

> if you want to brute force enumerate them But you don't. Even what you might call "brute force" Sudoku solvers start from the given hints in the puzzle, which reduce the search space considerably. Given a set of Sudoku hints with a unique solution, you won't need "years or eons" with even a very simple solver.

Yes, of course you don't, I think you misunderstood my comment. The comment I replied to was asking about true brute force enumeration of all boards -- not a solver that uses inferences based on the hints -- he guessed that you only need 9! * 9! total attempts which implies enumerating all boards and picking the one that matches the initial hints. This is in fact a constant time solution like he guessed, but it is also intractable.

A normal "very simple" solver of the kind you're talking about will solve the solution very quickly, in seconds or less, and it will also not be a constant time algorithm.

Post reply on HN