4 ms·

I 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

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

bitwize 9y ago
Reminds me of Watson's Jeopardy! exhibition match. Watson was right far more often than the humans, but when it was wrong it was way off base.
Undertow_ 9y ago
Probably an early-onset snowballing of what you said. When one wrong placement is made, it's pretty hard to recover for a full puzzle.
suddensleep 9y ago
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.
dahart 9y ago
I'm not certain, but based on the description by the author, this solver is sometimes doing probabilistic guessing. You're more likely to make a mistake early when you do this -- there are fewer chances to guess incorrectly near the end of the game as inferences grow stronger, and more chances in the beginning and middle to guess wrong which will then snowball into a more wrong answer. So statistically, it makes sense that failures tend to be large. I thought it was interesting that the "hard" category seemed to have more wrong answers than the 2 harder categories. Maybe there just aren't enough samples, but in the data shown in the table, it seems like a big difference.
CJefferson 9y ago
One big problem is the network is never trained on incorrect Sudokus, so at that point it's effectively into random guessing.
LanceH 9y ago
Once you get a few right, the solution spaces closes very fast. A valid sudoku puzzle has a unique solution, so if you had 90% correct, there would only be one thing to choose from for each of the other 9 spaces.

bitwize 9y ago

Reminds me of Watson's Jeopardy! exhibition match. Watson was right far more often than the humans, but when it was wrong it was way off base.

Undertow_ 9y ago

Probably an early-onset snowballing of what you said. When one wrong placement is made, it's pretty hard to recover for a full puzzle.

suddensleep 9y ago

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.

dahart 9y ago

I'm not certain, but based on the description by the author, this solver is sometimes doing probabilistic guessing. You're more likely to make a mistake early when you do this -- there are fewer chances to guess incorrectly near the end of the game as inferences grow stronger, and more chances in the beginning and middle to guess wrong which will then snowball into a more wrong answer. So statistically, it makes sense that failures tend to be large. I thought it was interesting that the "hard" category seemed to have more wrong answers than the 2 harder categories. Maybe there just aren't enough samples, but in the data shown in the table, it seems like a big difference.

CJefferson 9y ago

One big problem is the network is never trained on incorrect Sudokus, so at that point it's effectively into random guessing.

LanceH 9y ago

Once you get a few right, the solution spaces closes very fast. A valid sudoku puzzle has a unique solution, so if you had 90% correct, there would only be one thing to choose from for each of the other 9 spaces.