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

61–70 of 111 posts

Re: Can Neural Networks Crack Sudoku?

#61

Post by joshuata »

likelynew wrote: post #46
CJefferson wrote: post #33

Earlier quoted context omitted.

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.

Are you serious.. SAT solvers have some of the hardest code I have seen. Look at the SAT solvers that won satcompetition. On the other hand IMO, implementing a neural network on your own is very easy. But the point is not that. I consider the neural network libraries(e.g. tensorflow) as given, as it is in not related to the problem, and can be used in many different problems. I will consider only the code above the n…

Yes, competitive SAT solvers are very complicated. However, they are not outside of most developers' abilities. During a verification course at my University we had to build a simple SAT solver. Most students were able to complete the project in ~20-30 hours. Mine wasn't fast, but it worked well enough to be a proof of concept.

Also, saying that NN are easy with a library like tensorflow is akin to saying that Sudoku solvers are easy with Prolog. Of course they are! The library/language does the vast majority of the heavy lifting.

Re: Can Neural Networks Crack Sudoku?

#62

Post by monkeydust »

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.

Agree its impressive.

Re: Can Neural Networks Crack Sudoku?

#63

Post by iaw »

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'

Re: Can Neural Networks Crack Sudoku?

#64

Post by ska »

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 cases, but maybe it does.

[1] NB it's not immediately clear that OPs problem is in that class.

Re: Can Neural Networks Crack Sudoku?

#66

Post by jmull »

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…

> 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 understand NN pretty well (or aren't familiar with solving puzzles like Sudoku) won't.

Re: Can Neural Networks Crack Sudoku?

#67

Post by dahart »

tom_mellior wrote: post #54
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…

O(1) means bounded by a constant upper bound, not that every actual run of the program takes the exact same amount of time. Just like "simple quick sort is O(n^2)" does not mean that every invocation will take a quadratic amount of time. The parent's "can be solved in constant time" means the same thing, informally. Anyway, we are in agreement that enumerating all boards would be quite inefficient.

Are you claiming that all sudoku solvers are constant time algorithms, because the upper bound is not greater than enumerating the total constant number of boards? There are no O(1) sudoku solvers in existence that run in a short amount of time, yet you seem to be suggesting that the "very simple" sudoku solvers you referred to can be classified as O(1) algorithms.

Re: Can Neural Networks Crack Sudoku?

#68

Post by jcoffland »

wiredfool wrote: post #19

Soduku is trivially directly solvable for puzzles that are not in the hard/ultra hard level by propagating constraints. For cases where that's not possible, iterative approaches can be very effective -- with not particularly optimized python, the worst solution time I ever saw was 1 sec on a 1st gen eeepc netbook. That had about 6 layers of iterative backtracking before it came up with the solution.

I wrote a Soduku solver in Python while waiting in the airport on a long layover that solves even the most difficult puzzles in a few seconds on an now old laptop. It requires some backtracking but it's really not that hard.

Edit: I decided to publish my implementation on GitHub. https://github.com/jcoffland/fsudoku

Post reply on HN