Solving Sudoku Puzzles with Recurrent Neural Networks, Richard Zhu, UG '23 (3967706)
Recent advancements in machine learning have allowed for near-human or even superhuman performance in applications spanning chess-playing, protein folding, and natural language generation. Sudoku, a comparatively simpler task, appears to be an interesting problem. The puzzle can be modelled as a constraint or propositional satisfaction problem (CSP/SAT) which provides the basis for many backtracking-based solvers with 100% accuracy on 3x3 puzzles. However, for the general n x n case of the puzzle these algorithms are unproven and would at best run in exponential time with respect to n. This paper establishes a new state of the art test accuracy of 65.1% for 3x3 Sudoku puzzle solvers using a recurrent neural network (RNN) running in polynomial time. The accuracy is calculated across 10,000 unseen 3x3 Sudoku puzzles of medium difficulty (on average there are 48 blanks on the puzzle board) and is achieved with a shallow, bidirectional RNN with long-short term memory (LSTM) recurrent cell.