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.pyfor 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.pycreate sudoku games. You don't have to run this. Instead, download pre-generated games.hyperparams.pyincludes all adjustable hyper parameters.data_load.pyloads data and put them in queues so multiple mini-bach data are generated in parallel.modules.pycontains some wrapper functions.train.pyis for training.test.pyis 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.
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}}
}