VisioNxN Sudoku -

This project aims to solve any sudoku of N dimension, where N is a non-prime. The project uses pygame for creating the Graphical User Interface. The project is implemented in two forms -

• An option to load an image saved on the system or use the webcam to feed image to the program and then play the game on the system.
• An option to use Augmented Reality and solve the sudoku by showing the puzzle to the webcam.

The project uses Dancing Links in the form of Algorithm X to find the solution of the Sudoku puzzle. Sudoku is a well known NP-Complete problem and Algorithm X is a means of implementing a form of greedy depth first search to find the appropriate solution. For more understanding on the Sudoku Algorithm, read here. For understanding the Image Processing approach, read here.

You can find the complete concept and implementations explained in detail at the following blog posts -

• Augmented Reality Sudoku Solver — Part I
• Augmented Reality Sudoku Solver — Part II
• Augmented Reality Sudoku Solver — Part III
• Augmented Reality Sudoku Solver — Part IV

Index -

• Introduction
• Index
• Installation
  • Installing Pytorch
  • Installing other requirements
• How to Play
• Game Images
• Files in the repository
• Bibliography

Installation -

1. Installing Pytorch

Find the suitable pytorch release for your system here.

In my case, this command was used -

pip install torch==1.6.0+cpu torchvision==0.7.0+cpu -f https://download.pytorch.org/whl/torch_stable.html

2. Installing other requirements

pip3 install -r requirements.txt

or

pip install -r requirements.txt

How to play -

To play the game using GUI -

python3 main.py

To use the sudoku solver in CLI, edit the file according to the problem and run -

python3 cli_main.py

Game Images -

Opening Screen


Play Game


Sample Game Loaded


Load from file


Select File


Succesfully Loaded


Load from Camera: 9 X 9


Succesfully Loaded


Load from Camera: 8 X 8


Succesfully Loaded


Load from Camera: 6 X 6


Succesfully Loaded


Load from Camera: 4 X 4


Succesfully Loaded


When an invalid image is clicked


Start Playng the Game


Solving using the Solve Button


Game Won


Augmented Reality Option


Augmented Reality Test: 4 X 4


Augmented Reality Test: 6 X 6


Augmented Reality Test: 8 X 8


Augmented Reality Test: 9 X 9


Augmented Reality Test: 4 X 4


Augmented Reality Test: 6 X 6


Augmented Reality Test: 8 X 8


Augmented Reality Test: 9 X 9

Files in the Repository -

The files in the repository are :

GUI -

• __init__.py

  The __init__.py file is to make Python treat directories containing the file as packages.

• button.py

  This file contains the class for implementing a pygame button.

• camera_windows.py

  This file contains the class for implementing a camera screen in pygame.

Image_Processing -

• data

  This directory contains the images of digits used as the training dataset for the image classifier. It contains images pertaining to digits of the char74k dataset.

• char74k-cnn.pth

  It is the file containing the weights of the trained model on the data directory.

• char74k_dataset.tgz

  This zip file contains the complete char74k dataset.

• classifier.py

  This file contains the CNN Classifier for digit recognition.

• __init__.py

  The __init__.py file is to make Python treat directories containing the file as packages.

• process_image.py

  This file contains the class for recognition of the sudoku from image.

• pytorch_gpu_assist.py

  This file contains helper functions to implement training on GPUs.

• README.md

  This file contains details about the algorithm and its implementation.

Samples

This directory contains sample images of sudoku puzzles that can be used as test cases for loading the image from file option in the program.

Sudoku -

• DancingLinks.pdf

  This is a copy of the original paper written by Donald Knuth on the concept of Dancing Links.

• __init__.py

  The __init__.py file is to make Python treat directories containing the file as packages.

• README.md

  This file contains details about the algorithm and its implementation.

• sudoku.py

  This file contains class to solve Sudoku puzzle.

.images

This directory contains the images for the icons and other media for the README File.

cli_main.py

This file can be used to solve sudoku of any dimension using CLI.

game_window.py

This file contains the class for implementing the GUI for the program.

__init__.py

The __init__.py file is to make Python treat directories containing the file as packages.

main.py

This file is used as the driver code to start the program.

README.md

The Description file containing details about the repository. The file that you looking at right now.

requirements.txt

This file contains the respective packages needed to be installed. To install the respective packages, use -

sample.npy

This file contains the default sudoku puzzle which will get loaded incase not last loaded file is found.

Fun Fact: This specific puzzle is designed to work against backtracking as a solution for sudoku and will take almost forever to solve it using backtracking.

Bibliography

• Game Icon: Icon made by Freepik from flaticons.com.
• Camera Icon: Icon made by Freepik from flaticons.com.
• Home Icon: Icon made by Freepik from flaticons.com.
• Rounded Rectangle for Buttons: The code for making rounded rectangle surface in pygame is adapted from here.
• Char74k Dataset: The dataset used for training the CNN to recognize the digits can be found here.
• CNN Model: The Model Architecture is adapted from here.
• Sudoku Solver: The code for implementing Sudoku as an exact cover problem is adapted from here.