Repository files navigation

PyTorch implementation for the Neuro-Symbolic Sudoku Solver leveraging the power of Neural Logic Machines (NLM).Please note that this is not an officially supported Google product. This project is a direct application of work done as part of originalNLM project. We have applied NLM concept to solve more complex (Solving Sudoku) problems. We have also described the internal workings inMedium Blog.

⭐ Star us on GitHub — it helps!

Neural Logic Machine (NLM) is a neural-symbolic architecture for both inductive learning and logic reasoning. NLMs use tensors to represent logic predicates. This is done by grounding the predicate asTrue or False over a fixed set of objects. Based on the tensor representation, rules are implementedas neural operators that can be applied over the premise tensors and generate conclusion tensors. Learn more about NLM from thepaper.

We have used below boolean predicates as inputs to NLM architecture:

1. isRow(r, num): Does numbernum present in rowr inside Sudoku grid?
2. isColumn(c, num): Does numbernum present in columnc inside Sudoku grid?
3. isSubMat(r, c, num): Does numbernum present in 3x3 sub-matrix starting with rowr and columnc.

Note here thatisRow andisColumn are binary predicates andisSubMat is ternary predicate. We have stacked the results ofisRow andisColumn and inputted as binary predicate.

The core architecture of the model contains deep reinforcement learning leveraging representation power of first order logic predicates.

• Python 3.x
• PyTorch 0.4.0
• Jacinle. We use the versioned90c3a for this repo.
• Other required python packages specified byrequirements.txt. See the Installation.

Clone this repository:

git clone https://github.com/ashutosh1919/neuro-symbolic-sudoku-solver.git --recursive

InstallJacinle included as a submodule. You need to add the bin path to your globalPATH environment variable:

export PATH=<path_to_neural_logic_machines>/third_party/Jacinle/bin:$PATH

Create a conda environment for NLM, and install the requirements. This includes the required python packagesfrom both Jacinle and NLM. Most of the required packages have been included in the built-inanaconda package:

conda create -n nlm anacondaconda install pytorch torchvision -c pytorch

This repo is extension of original NLM repository. We haven't removed the codebase of problems solved in the base repository but we are only maintaining the Sudoku codebase in this repository.

Below is the file structure for the code we have added to original repository to understand things better.

The code indifflogic/envs/sudoku contains information about the environment for reinforcement learning.grid.py selects dataset randomly from1 Million Sudoku Dataset from Kaggle.grid_env.py creates reinforcement learning environment which can perform actions.

The code inscripts/sudoku/learn_policy.py trains the model whereasscripts/sudoku/inference.py generates prediction from trained model.

We also provide code to download dataset and pre-trained models.

Taking theSudoku task as an example.

# To download dataset and pre-trained models$ jac-run scripts/sudoku/download_data_mode.py# To train the model:$ jac-run scripts/sudoku/learn_policy.py --task sudoku --dump-dir models# To infer the model:$ jac-run scripts/sudoku/inference.py --task sudoku --load-checkpoint models/sudoku.pth

Below is the sample output that you should get after runninginference.py where the program will generate a problemSudoku grid and NLM model will solve it.

We have trained model with tuning with different parameters and we got below results.

Thanks goes to these wonderful people (emoji key):

Ashutosh Hathidara 💻🤔🚧🎨📖💬🔬

Lalit Pandey 💻📖🤔🚧🎨💬🔬

This project follows theall-contributors specification. Contributions of any kind welcome!

• Neural Logic MachinesPaper andGitHub Repository.
• Reinforce Algorithm & Policy Gradientpaper
• 1 Million Sudoku Dataset