51–60 of 111 posts
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.
(I still think it would fail spectacularly on "super-human" sudokus.)
Earlier quoted context omitted.
> 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 al…
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 and take just little over 13 TB of disk/RAM space :).
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?
The paper which showed that the general case of Sudoku is NP-complete was apparently this one [1] (Linked from wikipedia)
[1] http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf
Earlier quoted context omitted.
> 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 al…
Anyway, we are in agreement that enumerating all boards would be quite inefficient.
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…
Also, in my personal experience, SAT is currently applicable to more problems than Neural Networks (although that is changing as Neural Networks get applied to more things). You can use SAT solvers to solve any problem in NP (well, other things as well but it rapidly gets painful). That's a lot of problems!
Earlier quoted context omitted.
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.
Well, it is really more of a exact cover problem, which can be solved quite simply and elegantly with Knuth's algorithm X. A neural network isn't simpler in any sense of the word. You might as well throw a simulated annealer at the problem.
Great idea! I'm sure D-WAVE would be happy to work with you on a quantum sudoku solver.
> 1M games were generated using generate_sudoku.py for training. I've uploaded them on the Kaggle dataset storage. No need to do that. It would suffice to just include the random seed in the script so that its results are reproducible.
Coming up next: CNNs applied to training CNNs
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…
Now, neither will be that good at the job they are made for. But that is far from unique to this field. Consider, a car/bike/house/whatever is not exactly hard to build for backyard use. Getting world class, on the other hand, escalates to difficult very quickly.
Earlier quoted context omitted.
I am not saying it is not. My condition is in what if neural network can solve a problem without any domain knowledge. I think it's a huge win even if we don't understand anything about the solution. Be it well solved problems like approximate minimum distance in a graph to practically unsolvable like automatically proving unproved theorems in mathematics.
I take it this way. How many problems can you solve using knowing mostly exact cover. Not very many. But, if we can build ML systems that can solve mostly any problem(we can't today) even without giving any insight, I would say it will be one of the things whose impact will surpass anything. Note, I am not getting into AGI, just saying a system that can solve objective problems. And while sudoku is not a very good ex…
That is, the "exact cover" nature of Sudoku is not immediately obvious to everyone. At least, it wasn't obvious to me. Seeing how quickly you can map it to that and then get a solution was a lot of fun and ridiculously educational.