A more interesting problem would be to train an n x n sudoku and test the model on an m x m sudoku where m n. Does it make sense?
edit: formatting
Can Neural Networks Crack Sudoku?
11–20 of 111 posts
Re: Can Neural Networks Crack Sudoku?
#12Nail, meet hammer.
Re: Can Neural Networks Crack Sudoku?
#13I find it interesting that when the NN fails to complete the whole puzzle, it seems to fail spectacularly (github.com/Kyubyong/sudoku#results) -- that is, there aren't a lot of good-partial attempts (90% or above). Does anyone know why this might be the case? Does the first wrong placement of a number in a gap essentially ruin the rest of the guesses?
My intuition says yes; if a wrong number is placed in a square and then taken as ground truth for solving the rest of the puzzle, it certainly seems like the error would propagate.
As a concrete example, say you misplace a '2' somewhere within a given puzzle. Obviously, this cell is incorrect. But depending on the nature of what the NN has learned, it may believe the row (resp. column, 3x3 box constraint) already has the '2' in it, so tries to fill its correct spot with another number. Which of course then leads to the column and/or 3x3 box of that cell to learn an incorrect value, starting the process over again.
This same phenomenon can be seen in the game Kenken; depending on the strategies you use at any given point in the game, one mistake can propagate outward pretty quickly and spoil large sections of the puzzle.
Re: Can Neural Networks Crack Sudoku?
#14You can solve sudoku with a SAT solver. You don't need neural networks, this was an assignment in cs 251 at UIC.
yes, a NN isn't the best tool for the job. i guess it's just an experiment if one was able to do this with a reasonable rate of success.
Yeah, I figured as such. I assume you are trying to learn about NN?
Re: Can Neural Networks Crack Sudoku?
#15Re: Can Neural Networks Crack Sudoku?
#16You can solve sudoku with a SAT solver. You don't need neural networks, this was an assignment in cs 251 at UIC.
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.
Re: Can Neural Networks Crack Sudoku?
#17> 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.
Re: Can Neural Networks Crack Sudoku?
#18You can solve sudoku with a SAT solver. You don't need neural networks, this was an assignment in cs 251 at UIC.
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.
We did use a library for the SAT solving. Hmm didn't think of that though.
Re: Can Neural Networks Crack Sudoku?
#19Soduku 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.
Re: Can Neural Networks Crack Sudoku?
#20Every time sudoku comes up on HN I think back to when Ron Jeffries tried to solve it using Test Driven Development ;) http://ravimohan.blogspot.se/2007/04/learning-from-sudoku-so... - enjoy :D
I was going to say those really don't seem comparable, but after reading Jeffries', that really was awful.