sudoku

Can Convolutional Neural Networks Crack Sudoku Puzzles?

Sudoku is a popular number puzzle that requires you to fill blanks in a 9X9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids contains all of the digits from 1 to 9. There have been various approaches to solving that, including computational ones. In this project, I show that simple convolutional neural networks have the potential to crack Sudoku without any rule-based postprocessing.

Requirements

• NumPy >= 1.11.1
• TensorFlow == 1.1

Background

• To see what Sudoku is, check the wikipedia
• To investigate this task comprehensively, read through McGuire et al. 2013.

Dataset

• 1M games were generated using generate_sudoku.py for training. I’ve uploaded them on the Kaggle dataset storage. They are available here.
• 30 authentic games were collected from http://1sudoku.com.

Model description

• 10 blocks of convolution layers of kernel size 3.

File description

• generate_sudoku.py create sudoku games. You don’t have to run this. Instead, download pre-generated games.
• hyperparams.py includes all adjustable hyper parameters.
• data_load.py loads data and put them in queues so multiple mini-bach data are generated in parallel.
• modules.py contains some wrapper functions.
• train.py is for training.
• test.py is for test.

Training

• STEP 1. Download and extract training data.
• STEP 2. Run python train.py. Or download the pretrained file.

Test

• Run python test.py.

Evaluation Metric

Accuracy is defined as

Number of blanks where the prediction matched the solution / Number of blanks.

Results

After a couple of hours of training, the training curve seems to reach the optimum.

I use a simple trick in inference. Instead of cracking the whole blanks all at once, I fill in a single blank where the prediction is the most probable among the all predictions. As can be seen below, my model scored 0.86 in accuracy. Details are available in the `results` folder.

Level	Accuracy (#correct/#blanks=acc.)
Easy	47/47 = 1.00
Easy	45/45 = 1.00
Easy	47/47 = 1.00
Easy	45/45 = 1.00
Easy	47/47 = 1.00
Easy	46/46 = 1.00
Medium	33/53 = 0.62
Medium	55/55 = 1.00
Medium	55/55 = 1.00
Medium	53/53 = 1.00
Medium	33/52 = 0.63
Medium	51/56 = 0.91
Hard	29/56 = 0.52
Hard	55/55 = 1.00
Hard	27/55 = 0.49
Hard	57/57 = 1.00
Hard	35/55 = 0.64
Hard	15/56 = 0.27
Expert	56/56 = 1.00
Expert	55/55 = 1.00
Expert	54/54 = 1.00
Expert	55/55 = 1.00
Expert	17/55 = 0.31
Expert	54/54 = 1.00
Evil	50/50 = 1.00
Evil	50/50 = 1.00
Evil	49/49 = 1.00
Evil	28/53 = 0.53
Evil	51/51 = 1.00
Evil	51/51 = 1.00
Total Accuracy	1345/1568 = 0.86

References

If you use this code for research, please cite:

@misc{sudoku2018,
  author = {Park, Kyubyong},
  title = {Can Convolutional Neural Networks Crack Sudoku Puzzles?},
  year = {2018},
  publisher = {GitHub},
  journal = {GitHub repository},
  howpublished = {\url{https://github.com/Kyubyong/sudoku}}
}

Papers that referenced this repository

• OptNet: Differentiable Optimization as a Layer in Neural Networks
• Recurrent Relational Networks for Complex Relational Reasoning
• SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver