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

71–80 of 111 posts

Re: Can Neural Networks Crack Sudoku?

#71

Post by dahart »

mamon wrote: post #52
dahart wrote: post #40

Earlier quoted context omitted.

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 al…

9!*9! is just little over 131 billion dashboards. checking correctnes (no number is repeated in row or column) is as simple as counting a sum in all boxes, rows and columns. Generation of all possible boards is little more complex but I can hardly see how it could take "eons" - with proper implementation (Apache Spark :P ) and reasonably powerful hardware (1000 CPU core cluster, ha! ha! ha!) it should run under 1 day…

9! * 9! is not the number of boards, that is a bad estimate. If you don't account for symmetries, rotations, re-numberings and other things, the number of boards is 6.7e21. Even if you could check a full board in a nanosecond (which you can't) enumerating that number would take more than 200,000 cpu-years.

The paper linked to in the OP's article says: "Due to the sheer number of sudoku solution grids a brute force search would have been infeasible, but we found a better approach to make this project possible. Our software for exhaustively searching through a completed sudoku grid, named checker, was originally released in 2006. However, this first version was rather slow. Indeed, the paper [1] estimates that our original checker of late 2006 would take over 300,000 processor-years in order to search every sudoku grid."

https://arxiv.org/pdf/1201.0749.pdf

The estimate in the comment (9!*9!) seems to be implying a simple enumeration, not a complex strategy of symmetry-folding. But even if you do reduce the enumeration, the authors of that paper say their software requires 800 CPU years. I'm not making any claims about whether getting that down to a day might be possible, but I wish you good luck. By all means, show everyone how to do it with a proper implementation and a large cluster! ;)

Re: Can Neural Networks Crack Sudoku?

#72

Post by cityhall »

ska wrote: post #64
kortex wrote: post #42

So much missing-the-point in this thread. The point isn't "can we solve sudoku with a completely over-wrought solution", it's "can NN be applied to X class of problems with no human-added domain specific knowledge". And that I think is quite cool.

"can NN be applied to X class of problems with no human-added domain specific knowledge" Universal approximation theory suggest that for a significant class of problems, the answer to this is "obviously" [1]. The problem that remains is how effective is the learning. I'm not convinced applying them to areas like this one where the are clearly much better approaches teaches us anything useful for more interesting case…

Universal approximation just says there exists a solution, not that there's a reasonable way to find it with a bounded amount of training data. The networks used in proofs typically have contrived and impractical architectures.

Re: Can Neural Networks Crack Sudoku?

#74

Post by jcoffland »

kortex wrote: post #42

So much missing-the-point in this thread. The point isn't "can we solve sudoku with a completely over-wrought solution", it's "can NN be applied to X class of problems with no human-added domain specific knowledge". And that I think is quite cool.

> The point isn't "can we solve sudoku with a completely over-wrought solution", it's "can NN be applied to X class of problems with no human-added domain specific knowledge"

But why would you care about solving a class of problems with NNs when that class of problems already has much better solutions? Too many new programmers are running to NNs out of pure laziness. NNs are like magic. They solve the problem for you so you don't have to learn how to solve it yourself. Or at least that's the enticing promise.

Re: Can Neural Networks Crack Sudoku?

#76

Post by ska »

cityhall wrote: post #72
ska wrote: post #64

Earlier quoted context omitted.

"can NN be applied to X class of problems with no human-added domain specific knowledge" Universal approximation theory suggest that for a significant class of problems, the answer to this is "obviously" [1]. The problem that remains is how effective is the learning. I'm not convinced applying them to areas like this one where the are clearly much better approaches teaches us anything useful for more interesting case…

Universal approximation just says there exists a solution, not that there's a reasonable way to find it with a bounded amount of training data. The networks used in proofs typically have contrived and impractical architectures.

That's exactly what I meant by:

    The problem that remains is how effective is the learning.
The distinction I'm trying to draw is a tiny bit nuanced - since we know NN's are broadly applicable if we can figure out how to train them, the posters "can NN be used here" is really "can we figure out how to train it". My question is, since Sudoko solution obviously has better, non NN approaches, does spending time on that lead to anything generally useful, or would you be better off spending the same time working out how to train a NN on a more appropriate problem domain?

To late to add an comment to the original.

Re: Can Neural Networks Crack Sudoku?

#77

Post by ska »

jmull wrote: post #66
ska wrote: post #64

Earlier quoted context omitted.

"can NN be applied to X class of problems with no human-added domain specific knowledge" Universal approximation theory suggest that for a significant class of problems, the answer to this is "obviously" [1]. The problem that remains is how effective is the learning. I'm not convinced applying them to areas like this one where the are clearly much better approaches teaches us anything useful for more interesting case…

> teaches us anything useful... Maybe the useful thing here is that Sudoku is a problem space a lot of people understand pretty well even though it's not trivial. That makes a nice domain for thinking about and understanding NN. I guess that people who are familiar with the problem space of solving Sudoku and similar problems but who don't know much about NN will find this pretty interesting but people who already un…

I think your guess is reasonable. It's the reason I wasn't very prescriptive: i.e. NN is not a very sensible approach if the goal is a great Sudoku solver, but the exercise might have other value I just can't immediately see.

Re: Can Neural Networks Crack Sudoku?

#78

Post by bonzini »

jcoffland wrote: post #74
kortex wrote: post #42

So much missing-the-point in this thread. The point isn't "can we solve sudoku with a completely over-wrought solution", it's "can NN be applied to X class of problems with no human-added domain specific knowledge". And that I think is quite cool.

> The point isn't "can we solve sudoku with a completely over-wrought solution", it's "can NN be applied to X class of problems with no human-added domain specific knowledge" But why would you care about solving a class of problems with NNs when that class of problems already has much better solutions? Too many new programmers are running to NNs out of pure laziness. NNs are like magic. They solve the problem for you…

And especially when humans don't use intuition to solve it, but basically an inefficient version of the same algorithms that are used by computers.

Re: Can Neural Networks Crack Sudoku?

#79

Post by theptip »

timdellinger wrote: post #31

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…

To me, it's an interesting question to ask how well NNs can perform without hand-holding, i.e. can they figure out all of the complex strategies that humans have figured out, starting from a blank slate?

C.f. AlphaGo, which invented new strategies that proved interesting to human players.

Of course, if you're training your NN to solve a real-world problem, you wouldn't choose to train it in this way, you would do as you suggested and feed it as much relevant training data as possible, to give it a head-start.

(Your points RE: sizing and quantity of training data sound reasonable and are out of my expertise, so nothings to add there).

Re: Can Neural Networks Crack Sudoku?

#80

Post by SomeStupidPoint »

iaw wrote: post #63
timdellinger wrote: post #31

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…

I suspect there may be a method by which one could convert solved sudoku's into numerous candidate puzzles. I imagine strategically removing numbers from solved puzzles so as to reinforce the neural connections for solution and filter out possible 'noise'

My immediate thought was to generate training data by making up solved puzzles, and then removing numbers one at a time (while ensuring there's still a unique solution), with a few different branches at each step from an initial solution.

You could generate massive datasets that way -- it would be pretty easy to generate a few billion pre-images of a solution. I mean, a solution has 80 numbers and a puzzle about 20. 80 choose 20 is about 10^18, or a billion billion.

Post reply on HN