kyubyong / sudoku Goto Github PK

Can Neural Networks Crack Sudoku?

License: GNU General Public License v3.0

Python 100.00%

convolutional-neural-networks sudoku number puzzle

sudoku's Introduction

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

sudoku's People

Contributors

Stargazers

Watchers

Forkers

vyraun joseph-zhong jdc08161063 soledad89 allensmile benjamesbabala libardo1 jrifkin orchestor rgioai eternal1025 vnvdvc benstoffelen cfirmo33 vdt eiriksm muharremokutan jelitox scotttlin mfalconi abmantha davidmoore-io vermuz yak0xff hhy5277 sriharshakappala sudarshansarolkar pborreli unquietcode wongfree chiragsingla nexusminds agreme jue-jiang litmon s1162276945 lxchen2001 liuxmw8 godfather239 xdsoar soroushmehr tad-done codeaudit liqipap secp8x32 charlesakin loozy5331 melspectrum007 georgefengp palmchou amatsukan hzxhzzk ashang-dot-org davidtranno1 pankajmehar reiisky hageshogun qiaokangqi kevinlanov foolishboys wzzzrrrr jasonvank happy-forks afcarl mu94w varunreddy wangyendt yvznvr rfaustinoo rmxpzlb yaduvendra djsilv tjleizeng fymv2n5s suanmingde astro-britt ja-odur ankhaa8 lucifer-heaven atulgrover41 hoangcuong2011 tung73 yatingjiang thomasbahen shenlh dalerxli chenbiningbo b1sounours nready-rnd dasarisasidhar j1w2robxx theassyrian lesmemes dgamepuzzle lsturtew luwuming ananthanithin jwj1214 saugkim ehdrhks0104

sudoku's Issues

dead code reported by vulture

We used vulture (https://github.com/jendrikseipp/vulture) to search
for unused code in your project. You can find the report below. It
would be great if you could give us feedback about which items are
actually used or unused. This would allow us to improve vulture and
ideally it also helps you to remove obsolete code or even find typos
and bugs.

Command:

vulture sudoku

Results:

sudoku/generate_sudoku.py:11: Unused variable 'sample'
sudoku/generate_sudoku.py:157: Unused function 'display'
sudoku/train.py:58: Unused attribute 'merged'

There might be false positives, which can be prevented by adding them to a
whitelist file. You may find more info here

Regards,
vulture team

space or tab is a mess.

Space 2, space 4, tab 4....It's so a mess.

Issue on reproduce the work.

Just load the data and model.

python test.py

give me the following issue. Sounds model can not find in checkpoint. any pointer to this issue?

W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_1/variance not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_1/beta not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_1/gamma not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_9/variance not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_1/mean not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_10/beta not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_10/W not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_9/mean not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_1/W not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_10/gamma not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_10/variance not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_11/b not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_9/gamma not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_11/W not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_2/beta not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_10/mean not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_2/mean not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_2/W not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_2/variance not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_3/beta not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_2/gamma not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_9/beta not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_3/gamma not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_3/mean not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_4/W not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_4/beta not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_9/W not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_4/variance not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_4/gamma not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_5/W not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_3/W not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_4/mean not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_5/beta not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_3/variance not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_8/variance not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_5/mean not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_5/gamma not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_5/variance not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_6/mean not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_6/beta not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_6/W not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_8/mean not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_6/gamma not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_6/variance not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_7/gamma not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_7/W not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_8/gamma not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_7/beta not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_8/W not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_7/variance not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_7/mean not found in checkpoint
W tensorflow/core/framework/op_kernel.cc:975] Not found: Key lyr-conv_8/beta not found in checkpoint
Traceback (most recent call last):
  File "test.py", line 730, in <module>
    test1()
  File "test.py", line 650, in test1
    saver.restore(sess, tf.train.latest_checkpoint('asset/train/ckpt'))
  File "/Users/grant/project/sudoku/sudoku/lib/python2.7/site-packages/tensorflow/python/training/saver.py", line 1388, in restore
    {self.saver_def.filename_tensor_name: save_path})
  File "/Users/grant/project/sudoku/sudoku/lib/python2.7/site-packages/tensorflow/python/client/session.py", line 766, in run
    run_metadata_ptr)
  File "/Users/grant/project/sudoku/sudoku/lib/python2.7/site-packages/tensorflow/python/client/session.py", line 964, in _run
    feed_dict_string, options, run_metadata)
  File "/Users/grant/project/sudoku/sudoku/lib/python2.7/site-packages/tensorflow/python/client/session.py", line 1014, in _do_run
    target_list, options, run_metadata)
  File "/Users/grant/project/sudoku/sudoku/lib/python2.7/site-packages/tensorflow/python/client/session.py", line 1034, in _do_call
    raise type(e)(node_def, op, message)
tensorflow.python.framework.errors_impl.NotFoundError: Key lyr-conv_1/variance not found in checkpoint
	 [[Node: save/RestoreV2_6 = RestoreV2[dtypes=[DT_FLOAT], _device="/job:localhost/replica:0/task:0/cpu:0"](_recv_save/Const_0, save/RestoreV2_6/tensor_names, save/RestoreV2_6/shape_and_slices)]]

Caused by op u'save/RestoreV2_6', defined at:
  File "test.py", line 730, in <module>
    test1()
  File "test.py", line 649, in test1
    saver = tf.train.Saver()
  File "/Users/grant/project/sudoku/sudoku/lib/python2.7/site-packages/tensorflow/python/training/saver.py", line 1000, in __init__
    self.build()
  File "/Users/grant/project/sudoku/sudoku/lib/python2.7/site-packages/tensorflow/python/training/saver.py", line 1030, in build
    restore_sequentially=self._restore_sequentially)
  File "/Users/grant/project/sudoku/sudoku/lib/python2.7/site-packages/tensorflow/python/training/saver.py", line 624, in build
    restore_sequentially, reshape)
  File "/Users/grant/project/sudoku/sudoku/lib/python2.7/site-packages/tensorflow/python/training/saver.py", line 361, in _AddRestoreOps
    tensors = self.restore_op(filename_tensor, saveable, preferred_shard)
  File "/Users/grant/project/sudoku/sudoku/lib/python2.7/site-packages/tensorflow/python/training/saver.py", line 200, in restore_op
    [spec.tensor.dtype])[0])
  File "/Users/grant/project/sudoku/sudoku/lib/python2.7/site-packages/tensorflow/python/ops/gen_io_ops.py", line 441, in restore_v2
    dtypes=dtypes, name=name)
  File "/Users/grant/project/sudoku/sudoku/lib/python2.7/site-packages/tensorflow/python/framework/op_def_library.py", line 759, in apply_op
    op_def=op_def)
  File "/Users/grant/project/sudoku/sudoku/lib/python2.7/site-packages/tensorflow/python/framework/ops.py", line 2240, in create_op
    original_op=self._default_original_op, op_def=op_def)
  File "/Users/grant/project/sudoku/sudoku/lib/python2.7/site-packages/tensorflow/python/framework/ops.py", line 1128, in __init__
    self._traceback = _extract_stack()

NotFoundError (see above for traceback): Key lyr-conv_1/variance not found in checkpoint
	 [[Node: save/RestoreV2_6 = RestoreV2[dtypes=[DT_FLOAT], _device="/job:localhost/replica:0/task:0/cpu:0"](_recv_save/Const_0, save/RestoreV2_6/tensor_names, save/RestoreV2_6/shape_and_slices)]]

How it it different or better from applying backtracking algorithm?

We arrive at solutions in less time by backtracking also. In this sense , I want to ask that are there any practical implications for this neural net ?

By the way, I am beginner in deep learning.

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.