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

81–90 of 111 posts

Re: Can Neural Networks Crack Sudoku?

#81

Post by dgfgfdagasdfgfa »

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…

Well, sudoku is a solved problem. This would amount to teaching a neural net graph coloring.

Re: Can Neural Networks Crack Sudoku?

#82

Post by tom_mellior »

dahart wrote: post #67
tom_mellior wrote: post #54

Earlier quoted context omitted.

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.

I'm claiming it's possible to write Sudoku solvers that have some constant upper bound on execution time. If you read this as "a short amount of time", you are misreading it.

I'm also not saying that this is true for all Sudoku solvers, since you could write one that sometimes just decides to uselessly burn cycles for a few centuries before returning a correct solution.

Here's that simple argument again: Sudoku can be solved in time at most exponential in the input size. The input size of 9x9 Sudoku is constant. The exponential of that constant is a constant. Not a very interesting argument? I agree, so I'm dropping this now.

Re: Can Neural Networks Crack Sudoku?

#83

Post by namuol »

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…

> 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?

Re: Can Neural Networks Crack Sudoku?

#84

Post by std_throwaway »

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?

Can we say that the number of possible states that the universe can assume is finite? Can we further conclude that everything that is possible must fit within the boundaries of the universe and therefore everything is either O(1) or unrealistic?

Re: Can Neural Networks Crack Sudoku?

#85

Post by dkersten »

dgfgfdagasdfgfa wrote: post #81
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…

Well, sudoku is a solved problem. This would amount to teaching a neural net graph coloring.

There's a very elegant solution using dancing links, I wonder could you teach a NN to essentially do that. Somehow.

Re: Can Neural Networks Crack Sudoku?

#86

Post by [deleted] »

jcoffland wrote: post #68
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

[deleted]

Re: Can Neural Networks Crack Sudoku?

#87

Post by wiredfool »

jcoffland wrote: post #68
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

Yeah, I was seeing if I could do the complete solution faster than a single solution. But I was at the inlaw's dinner table, not the airport.

This is it, uploaded a few years later in a repo for soduku over sms:

https://github.com/wiredfool/sms-doku/blob/master/so.py

Re: Can Neural Networks Crack Sudoku?

#88

Post by PaulHoule »

theptip wrote: post #79
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…

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, see

https://en.wikipedia.org/wiki/Satisfiability_modulo_theories

adding a neural net to it doesn't help in any way.

Re: Can Neural Networks Crack Sudoku?

#89

Post by faragon »

I would like to know if can be proven that NN for problems involving permutations can be as efficient as a SAT solver, less, or more efficient (e.g. if using the training just as a acceleration avoid learning futile permutations works for saving training time, or if it is not noticeable)

Re: Can Neural Networks Crack Sudoku?

#90

Post by nojvek »

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 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 singlets e.t.c and build a really fast sudoku solver with 100% accuracy. All this happening in a matter of seconds.

Post reply on HN