Using 10 convolutional layers seems questionable - the precise values and location of each number is essential for getting the right answer, so it seems like the model design is poorly suited to the task. The obvious approach to me would be to train a neural net to be a heuristic to order exploration in a constraint satisfaction solver, mirroring how AlphaGo combines monte carlo search trees with neural nets. Might net a nice speed up.
Can Neural Networks Crack Sudoku?
91–100 of 111 posts
Re: Can Neural Networks Crack Sudoku?
#92Interesting -- there must be a large literature on neural nets and NP-completeness, no?
Re: Can Neural Networks Crack Sudoku?
#93To 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 just feel bad about this "my intuition is that you'll need more layers than 10 in the NN, and much much more data." I still find current AI as basically a filter. Image to text, speech to text e.tc A smart AI would be able to figure out sudoku rules from a very small sample of games, it would then figure out a rudimentary backtracking algorithm. It would then sleep over it and figure out more patterns like naked si…
When a pig suddenly starts to dance the remarkable thing is not that it can not do a tango, but that it can dance at all.
Re: Can Neural Networks Crack Sudoku?
#94Earlier quoted context omitted.
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…
There is a very simple strategy that solves all Sudoku puzzles. Pick one open square, try a number that is possible for that, backtrack if you get stuck. For better results, pick the open square which has the fewest number of possible choices. Human solvers might try something more efficient, but the above strategy is not at all bad for computer implementation. It's very much a solved problem with existing technology…
Yeah, yeah, sudoku is easy for computers. That's not the point. The point is learning about neural networks. So yeah, "adding a neural net" does help with that.
Re: Can Neural Networks Crack Sudoku?
#95Earlier quoted context omitted.
There is a very simple strategy that solves all Sudoku puzzles. Pick one open square, try a number that is possible for that, backtrack if you get stuck. For better results, pick the open square which has the fewest number of possible choices. Human solvers might try something more efficient, but the above strategy is not at all bad for computer implementation. It's very much a solved problem with existing technology…
Yeah, yeah, sudoku is easy for computers. That's not the point. The point is learning about neural networks. So yeah, "adding a neural net" does help with that.
In which case the hard part is finding a suitable problem; you might be better off learning about SMT solvers because you don't have Marc Cuban telling everybody to do it.
Re: Can Neural Networks Crack Sudoku?
#96As a combinatorial optimization problem, integer programming is the best tool for solving Sudoku. Fast, accurate, and guarantees the optimality of the solution. I'm impressed at how well this neural network did anyway though!
Re: Can Neural Networks Crack Sudoku?
#97You can solve sudoku with a SAT solver. You don't need neural networks, this was an assignment in cs 251 at UIC.
SAT - Satisfiability
https://en.wikipedia.org/wiki/Boolean_satisfiability_problem
Acronyms are always a pet peeve of mine. I would know what a SAT is - since I've spent more than 50% of my life with Computer Science. However, not many people would understand the acronym you'd use. So, it would be great if in general one mentions what SAT refers to rather than using the acronym. Mention the long form the first time and then use the short form later in your sentence.
Sorry if this came across as too affront, just a personal observation. I saw this a couple of ago with GRUs on another thread too.
Re: Can Neural Networks Crack Sudoku?
#98Earlier quoted context omitted.
> 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.
Implications around strategy learning, reinforcement, and learning logical systems.
Re: Can Neural Networks Crack Sudoku?
#99Earlier quoted context omitted.
> 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…
> why would you care about solving a class of problems with NNs when that class of problems already has much better solutions? > NNs are like magic. They solve the problem for you so you don't have to learn how to solve it yourself. Sounds like you answered your own question; am I missing something?
The part you are missing is that the magic is illusory.
Re: Can Neural Networks Crack Sudoku?
#100Earlier quoted context omitted.
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.
Implications around strategy learning, reinforcement, and learning logical systems.
The point is - would you do better off on these with a more applicable problem domain? Do the things you learn transfer there well?
It's not obvious.