Sudoku-Solvers

Exploring the different algorithms to solve Sudoku

Instructions

Installing gym-sudoku From Forked Repo

1. git clone https://github.com/jamesdvance/gym-sudoku.git
2. pip install ./gym-sudoku

Background

Soduku is played on a grid of 9 x 9 spaces. Within the rows and columns are 9 “squares” (made up of 3 x 3 spaces).
Each row, column and square (9 spaces each) needs to be filled out with the numbers 1-9,
without repeating any numbers within the row, column or square.

To my knowledge, no one has yet succeeded in solving Sudoku as a pure reinforcement learning problem. Sakin et all [4] managed to train an accurate supervised classifer that could predict the winning outcome of a game. However, the solution does not come up with new solutions and cannot perform multiple solutions on the same problem.

Of course its trivial to solve Sodoku as a Linear Program. It's such a common formulation that it is the example problem in the PulP library documentation. It is also straightforward to solve as a programming problem, including a simple depth-first search approach.

Solutions

Depth First Search (Memory Optimized)
Linear Programming

Resources

Depth First Search

1. Sudoku Leetcode problem

Linear Programming

2. Sudoku As A Linear Program
3. Sudoku As Graph Coloring Problem

Reinforcement Learning

4. Sudoku-Gym Original
5. Reinforcement Learning For Constraint Satisfaction Game Agents
6. Sudoku with Deep Q Learning
   • Seems implausible

Supervised Learning

7. Can Convolutional Neural Networks Crack Sudoku Puzzles?
   • Fork Of Above With Pytorch
   • Paper: Solving Sudoku With Neural Networks
8. Supervised Learning with CNNs (99% accuracy)
9. OptNet: Differentiable Optimization As A Layer In Neural Networks
10. One Million Sudoku Games Dataset