Code Monkey home page Code Monkey logo

sudoku-solver-ai's Introduction

Sudoku AI

Auteur

Visuel

Rendu de l'algorithme sur une grille

Description

Programme personnel développé en Python permettant de scanner une grille de Sudoku et de la résoudre, avant d'afficher la réponse aux cases manquantes sur la grille.

Implémentation

Le programme a été développé en Python en utilisant principalement les bibliothèques opencv (cv2) et numpy pour le traitement d'image. La reconnaissance des chiffres est effectuée à l'aide de Keras / Tensorflow sur un modèle entraîné sur un dataset custom de 44 321 images issues d'un premier livre de Sudoku.

Les images présentes dans test sont issues d'un second livre de Sudoku qui n'a pas participé à l'élaboration du dataset.

Installation

Récupération des sources

  • Depuis l'invité de commandes (HTTP):
$ git clone https://github.com/jeunotca/sudoku-solver-ai.git
$ cd sudoku-solver-ai

OU

  • Depuis l'invité de commandes (SSH):
$ git clone [email protected]:jeunotca/sudoku-solver-ai.git
$ cd sudoku-solver-ai

OU

  • En téléchargeant les sources puis en extrayant l'archive

Installation

$ pip install -r requirements.txt

OU

  • En téléchargeant les sources puis en extrayant l'archive

Utilisation

Exécution du projet

$ python3 main.py

Dans cette situation, l'algorithme traitera l'image définie dans default.py. Sinon, il est également possible de choisir une image en utilisant

$ python3 main.py -i chemin/de/l/image.jpg

Dans les deux cas, la solution sera enregistrée au même endroit que l'image d'origine au format nom-image-d-origine-result.jpg.

Algorithme

Rendu de l'algorithme sur une grille

L'image subit d'abord un premier traitement, elle est convertie en niveaux de gris.

Rendu de l'algorithme sur une grille

Elle fait ensuite l'objet d'un flou gaussien de kernel 11 pour éliminer les impuretés.

Rendu de l'algorithme sur une grille

Un seuillage adaptatif est ensuite appliqué.

Rendu de l'algorithme sur une grille

Puis les couleurs de l'image sont inversées.

Rendu de l'algorithme sur une grille

Les contours de l'image sont ensuite trouvées à l'aide d'un filtre de Canny.

Rendu de l'algorithme sur une grille

On cherche alors le plus gros contour carré présent, supposé être la grille.

Cette grille subit ensuite une déformation de perspective pour améliorer l'image et donc l'efficacité de l'IA.

Rendu de l'algorithme sur une grille

Cette nouvelle matrice est découpée en 81 matrices de même taillées, donnant 81 cellules ressemblant à ceci :

Rendu de l'algorithme sur une grille

Si des pixels blancs sont détectés au centre de l'image, celle-ci est envoyée à un réseau de neurones.

Une fois toutes les cases identifiées, on résout la grille. Une première idée était d'utiliser du backtracking, mais le temps passé à résoudre une grille n'était pas négligeable. J'ai donc cherché une réduction de Karp vers d'autres problèmes. En particulier, le problème de couverture exacte se prête bien à l'exercice. J'ai donc utilisé le très rapidealgorithme X de Knuth. J'ai pour cela utilisé une implémentation déjà existante de la résolution d'une grille de Sudoku.

Après cela, il suffit d'afficher sur une image de la taille de perspective les chiffres manquants :

Rendu de l'algorithme sur une grille

On applique ensuite le changement inverse de perspective :

Rendu de l'algorithme sur une grille

Avant de simplement additionner les deux images :

Rendu de l'algorithme sur une grille

Les coefficients sont simplement additionnés afin de donner un effet "impacté par l'éclairage".

AI

  • L'IA utilisée est la suivante :
    • Fully connected de 784
    • Conv2D 32 filtres, kernel de 3, stride de 1, fonction ReLU
    • Batch normalization
    • Conv2D 32 filtres, kernel de 3, stride de 1, fonction ReLU
    • Batch normalization
    • Conv2D 32 filtres, kernel de 5, stride de 1, fonction ReLU
    • Batch normalization
    • Dropout de 0.4
    • Conv2D 64 filtres, kernel de 3, stride de 1, fonction ReLU
    • Batch normalization
    • Conv2D 64 filtres, kernel de 3, stride de 1, fonction ReLU
    • Batch normalization
    • Conv2D 64 filtres, kernel de 5, stride de 1, fonction ReLU
    • Batch normalization
    • Dropout de 0.4
    • Fully connected de 128, fonction ReLU
    • Dropout de 0.3
    • Fully connected de 128, fonction ReLU
    • Dropout de 0.4
    • Fully connected de 10, fonction softmax

Optimizeur Adam de learning rate = 1e-4 et loss function Sparse categorical crossentropy

Ce modèle a été réalisé en collaboration avec Michael Gellenoncourt.

L'IA a un taux de réussite de 99.78% sur nos tests.

Dossier AI

Le dossier AI contient le modèle que nous avons utilisé, ainsi que des fonctions permettant si vous le souhaitez de créer vos propres modèles à l'aide des images situées dans le dossier dataset/raw.

sudoku-solver-ai's People

Contributors

alexandrejeunotcaire avatar michaelgellenoncourt avatar

Watchers

 avatar  avatar

Recommend Projects

  • React photo React

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

  • Vue.js photo Vue.js

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

  • Typescript photo Typescript

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

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo 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.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

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

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.