Reply to post: Author here

Author here

Hey. Rasmus, author of the paper here. I'm glad you're all interested in my work :)

I just want to comment that you're correct that solving Sudokus with a computer is in itself not very interesting. It's been done a hundred times over, and almost all of the algorithms are superior to the RRN in almost every respect (simpler, faster, more accurate, etc.).

But, the RRN can do one thing the original methods cannot: it can interface with other deep learning models and be trained end-to-end. That means it can be added to e.g. a convolutional neural network and the combined model can be trained together to, e.g. reason about an image. The original Deepmind paper shows how to do this. Since they showed how to do the interfacing part, we focused solely on improving the "reasoning" aspect. We picked Sudoku since it requires an order of magnitude more steps of reasoning than the problems in the Deepmind paper. It's simply a test-bed to show how to solve "complex" reasoning problems (complex compared to the previous work in the area). We don't care about solving Sudokus in and of itself. I tried to make this clear in the paper, but it wasn't really picked up in this story.

"Solving Sudokus computationally is in itself not a very laudable goal, as traditional symbolic and hand-crafted algorithms like constraint propagation and search can solve any Sudoku in fractions of a second. For a good explanation and code, see Norvig (2006). Many other symbolic algorithms exist that can also solve Sudokus, like dancing links (Knuth, 2000) and integer programming. These algorithms are superior in almost every respect but one: they don’t comply with the interface, as they don’t operate on a set of vectors, and they’re not differentiable. As such they cannot be used in a combined model with a deep learning perceptual front-end."

Now there's one "traditional" "general purpose" algorithm that I know of that also work on real valued vectors and is differentiable, which is loopy belief propagation. We compared the trained RRN to this algorithm and found that the RRN learned a better algorithm, solving 96.6% vs. 92.5% of the hardest (17 givens) Sudokus. This version of loopy belief propagation was heavily modified for solving Sudokus. A more standard implementation solved 61.7%. Given the widespread use of loopy belief propagation it's exciting to wonder how many more applications could benefit from replacing the loopy BP with a trained RRN. Now, the RRN is a lot more complex, requires many more flops than loopy BP, and requires training, etc. so it's not a clear cut, search and replace job.

Best,

Rasmus