This is easy and you can find the code to do it on GitHub (I did). But what if it's in a jpg
Pour ce projet, on va donc importer une grille de sudoku depuis une page web pour la résoudre et la renvoyer remplie, sous format jpeg, avec une écriture manuscrite. La méthode employée se sépare en plusieurs étapes :
On commence par importer des bibliothèques utiles pour importer, traiter les images entre autres.
import requests
import numpy as np
import matplotlib.pyplot as plt
from skimage import io, transform
from copy import deepcopy
from PIL import Image
On va chercher des grilles sur un site dédié. J'avais initialement prévu de prendre une grille aléatoirement parmi celle du site, mais puisque la reconnaissance des caractères n'est pas encore fiable à 100%, j'ai choisi de fixer une grille, la n°6733, pour pouvoir contourner les erreurs de l'OCR et tester la fin du programme.
#num = np.random.randint(10000) #6733
num = 6733 # Je fixe un sudoku pour les tests
response = requests.get('http://www.planete-sudoku.com/generate-grande-grille.php?id_grille=' + str(num))
file = open("sudoku.jpg", "wb")
file.write(response.content)
file.close()
sudoku = io.imread('./sudoku.jpg')
plt.imshow(sudoku)
<matplotlib.image.AxesImage at 0x1af0027fb80>
Ensuite, on va traduire la grille sous forme d'un tableau d'images représentant chacune un chiffre.
np.shape(sudoku)
(435, 420)
Connaissant le format du sudoku, propre à ceux de planete-sudoku, on peut le rogner pour obtenir un carré de côté multiple de 9, pour faciliter la division en cases. Ici, je rogne à 414 pixels de côté, 414 étant le plus grand multiple de 9 inférieur à 420.
Ceci n'est adapté que pour les sudoku que l'on a importé, mais pour un fonction plus générale, il aurait fallu rogner intelligemment l'image autour de la grille du jeu puis s'assurer qu'une erreur de 8 pixels est encore négligeable dans la séparation des cases par la suite. On pourrait même détecter un sudoku que l'on aurait pris en photo pour approfondir et élargir l'usage, mais ici je me contente de traiter un format spécifique.
sudoku = sudoku[:414,:414]
image_de_depart = deepcopy(sudoku) # On duplique le sudoku pour comparer à la fin
On va isoler chaque case du sudoku, et les ranger dans un tableau. J'introduis une marge pour ne pas garder les pixels des lignes du sudoku. La fonction découpe se charge de créer une image 28x28 correspondant à la case aux coordonnées indiquées. Ces images sont en négatif, et calibrées pour s'adapter au format des échantillons sur lesquels on s'entraîne.
c = 46 #414/9 # côté d'une case
def decoupe(im,coordonnées):
a, b = coordonnées
marge = 2 # arbitrairement
case = im[a*c+marge:(a+1)*c-marge,b*c+marge:(b+1)*c-marge]
case = transform.resize(case, (28,28))
case[case > .6] = 1
negatif = 1. - case # Pour respecter le format des images de la méthode de reconnaissance
return negatif
plt.imshow(decoupe(sudoku,(4,1)))
<matplotlib.image.AxesImage at 0x1af002df910>
np.shape(decoupe(sudoku,(5,7)))
(28, 28)
cases = [[np.reshape(decoupe(sudoku,(i,j)),784) for j in range(9)] for i in range(9)]
cases[4][1]
array([0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0.74485294,
0.93161765, 1. , 0.76764706, 0.41911765, 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0.68357843, 0.97720588, 1. , 1. , 1. ,
1. , 1. , 0.7747549 , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0.53676471, 1. , 1. ,
0.93014706, 0.79901961, 0.75196078, 0.80661765, 0.96911765,
1. , 0.71985294, 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0.95367647, 1. , 0.88455882, 0. , 0. ,
0. , 0. , 0. , 1. , 1. ,
0.47377451, 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0.51862745, 1. , 1. ,
0.49730392, 0. , 0. , 0. , 0. ,
0. , 0.65147059, 1. , 0.79877451, 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0.6620098 , 1. , 1. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
1. , 0.89142157, 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0.75098039, 1. ,
1. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 1. , 0.94607843,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0.68259804, 1. , 1. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0.41985294, 1. , 0.97034314, 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0.4252451 ,
1. , 1. , 0.48970588, 0. , 0. ,
0. , 0. , 0. , 0.79044118, 1. ,
1. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0.93161765, 1. ,
0.95367647, 0.48970588, 0. , 0. , 0. ,
0.75269608, 1. , 1. , 1. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0.44436275, 0.97671569, 1. , 1. ,
1. , 1. , 1. , 0.97720588, 0.70073529,
1. , 0.99264706, 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0.58112745, 1. , 1. , 1. , 1. ,
0.95367647, 0.44338235, 0. , 1. , 0.96985294,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0.6127451 , 0.75098039, 0.6120098 , 0. , 0. ,
0. , 1. , 0.92279412, 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0.67426471, 1. ,
0.85294118, 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0.93161765, 1. , 0.72916667, 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0.51862745, 1. , 1. , 0.47377451, 0. ,
0. , 0. , 0. , 0.56813725, 1. ,
1. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0.97720588,
1. , 0.95367647, 0.53676471, 0. , 0. ,
0.69926471, 0.97720588, 1. , 0.72205882, 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0.48970588, 1. , 1. ,
1. , 1. , 1. , 1. , 1. ,
0.86102941, 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0.52083333, 0.86838235, 0.96176471, 1. ,
0.97720588, 0.88382353, 0.69926471, 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. , 0. ,
0. , 0. , 0. , 0. ])
On va faire un nouveau tableau, où on rangera les chiffres reconnus.
Cette partie est longue à charger (pour moi ça a pris une bonne demi-heure) et ne doit être exécutée qu'une seule fois. C'est la fameuse partie d'apprentissage de l'automate, qui n'est pas encore suffisante pour recopier exactement le sudoku.
from sklearn.datasets import fetch_openml
mnist = fetch_openml(data_id=554) # https://www.openml.org/d/554
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(mnist.data,
mnist.target.astype('int'), #targets str to int convert
test_size=1/7.0,
random_state=0)
from sklearn.linear_model import LogisticRegression
clf = LogisticRegression(fit_intercept=True,
multi_class='auto',
penalty='l1', #lasso regression
solver='saga',
max_iter=1000,
C=50,
verbose=2, # output progress
n_jobs=5, # parallelize over 5 processes
tol=0.01
)
clf
LogisticRegression(C=50, max_iter=1000, n_jobs=4, penalty='l1', solver='saga',
tol=0.01, verbose=2)
clf.fit(X_train, y_train)
[Parallel(n_jobs=4)]: Using backend ThreadingBackend with 4 concurrent workers.
convergence after 47 epochs took 2287 seconds
[Parallel(n_jobs=4)]: Done 1 out of 1 | elapsed: 38.1min finished
LogisticRegression(C=50, max_iter=1000, n_jobs=4, penalty='l1', solver='saga',
tol=0.01, verbose=2)
print(clf.predict(X_test[0:9]))
print(y_test[0:9])
[0 4 1 2 4 7 7 1 1] [0 4 1 2 7 9 7 1 1]
score = clf.score(X_test, y_test)
score
0.9195
J'ai eu un score de 0.9194. Le taux d'erreur est encore grand, c'est pourquoi la reconnaissance n'est pas fiable pour transcrire le sudoku en matrice et espérer le résoudre. Néanmoins, c'est une méthode que je peux appliquer à chacune des cases extraites du sudoku.
np.shape(X_test[0])
(784,)
plt.imshow(np.reshape(X_test[0],(28,28)))
<matplotlib.image.AxesImage at 0x1af1b728d90>
On fait maintenant un premier test sur une ligne du sudoku.
print(clf.predict(cases[0]))
[9 5 5 5 3 5 7 5 5]
On voit que dans la reconnaissance des chiffres, les cases vides sont identifiées au chiffre 5. On va donc les traiter à part en les remplaçant par zéro avant de traduire les autres chiffres du sudoku.
On représente une case vide par le chiffre 0. On ne traite une case que si un certain nombre de pixels sont sombres. Aussi on cherche un seuil approprié.
np.sum(cases[0][3]) # Ceci est un test pour trouver un seuil adapté
12.627450980392037
def retranscription(sudoku):
grille = np.zeros((9,9),int)
for i in range(9):
for j in range(9):
im = sudoku[i][j]
if sum(im)> 20 : # Le seuil à partir duquel on teste les chiffres
grille[i][j]=clf.predict([sudoku[i][j]])
return grille
grille_trad = retranscription(cases)
print (grille_trad)
[[9 0 0 0 3 5 7 0 0] [2 8 5 4 0 0 0 0 8] [0 0 0 0 0 0 2 2 5] [0 0 0 0 8 3 8 5 0] [0 9 0 0 0 0 0 8 0] [0 5 5 5 4 0 0 0 0] [5 5 3 0 0 0 0 0 0] [3 0 0 0 0 4 8 8 5] [0 0 9 5 8 0 0 0 3]]
plt.imshow(image_de_depart) # Pour comparer
<matplotlib.image.AxesImage at 0x1af003b2d30>
On constate qu'il y a encore beaucoup trop d'erreurs pour espérer recopier proprement et résoudre le sudoku...
J'ai tenté aussi une méthode utilisant Tesseract, mais la reconnaissance nécessitait l'enregistrement des cases en images, et cela m'a semblé trop lourd et laborieux pour l'usage qu'on en faisait. Mon essai suivant était avec OpenCV, mais je ne le laisse pas ici pour ne pas alourdir le code, et parce que ce n'est pas totalement abouti.
Ce bout de code est essentiellement tiré du programme d'un étudiant de Blaise Pascal basé sur le «Back-Tracking». Il s'est aussi intéressé à l'échelle permettant d'évaluer la difficulté d'un sudoku. Là, avec les informations dont on dispose, on peut par exemple situer le niveau du sudoku grâce au nombre de chiffres testés lors de la résolution.
#grille_t = grille_trad.tolist() # A utiliser si on est sûr de l'exactitude de la transcription
# En attendant de perfectionner la reconnaissance des caractères :
grille_av = [[9,0,0,0,3,5,7,0,0],[2,1,5,4,0,0,0,0,9],[0,0,0,0,0,0,2,4,5],[0,0,0,0,6,3,8,5,0],[0,9,0,0,0,0,0,6,0],[0,8,1,5,4,0,0,0,0],[1,6,7,0,0,0,0,0,0],[3,0,0,0,0,4,1,8,6],[0,0,4,6,1,0,0,0,7]]
grille_t = [[9,0,0,0,3,5,7,0,0],[2,1,5,4,0,0,0,0,9],[0,0,0,0,0,0,2,4,5],[0,0,0,0,6,3,8,5,0],[0,9,0,0,0,0,0,6,0],[0,8,1,5,4,0,0,0,0],[1,6,7,0,0,0,0,0,0],[3,0,0,0,0,4,1,8,6],[0,0,4,6,1,0,0,0,7]]
grille_d = [[9,0,0,1,0,0,0,0,5],[0,0,5,0,9,0,2,0,1],[8,0,0,0,4,0,0,0,0],[0,0,0,0,8,0,0,0,0],[0,0,0,7,0,0,0,0,0],[0,0,0,0,2,6,0,0,9],[2,0,0,3,0,0,0,0,6],[0,0,0,2,0,0,9,0,0],[0,0,1,9,0,4,5,7,0]]
iteration = 0 # pour compter le nombre d'appels à la fonction est_valide
test = 0 # pour compter le nombre de chiffres testés lors de la résolution
def affichage(grille): # Fonction qui affiche la grille comme un sudoku réel dans la console
for l in range(9):
lig = ""
for c in range(9) :
lig += str(grille[l][c])
if (c+1)%3 ==0:
lig += " "
print(lig)
if 0==(l+1)%3:
print("------------------")
#k=chiffre a placer , grille=grille qu'on va changer, l= ligne concernée, c= colonne concernée
def absent_sur_ligne(k, grille, l): # Fonction qui vérifie si le chiffre 'k' est deja présent sur la ligne
for c in range(9):
if grille[l][c] == k:
return False
return True
def absent_sur_colonne(k, grille, c): # Fonction qui vérifie si le chiffre 'k' est deja présent sur la colonne
for l in range(9):
if grille[l][c] == k:
return False
return True
def absent_sur_bloc(k , grille , l , c): # Fonction qui vérifie si le chiffre 'k' est deja présent sur le bloc
_l = l-(l%3)
_c = c-(c%3)
for c in range(_c,_c+3):
for l in range(_l,_l+3):
if grille[l][c] == k:
return False
return True
def est_valide(grille , position): # Fonction qui vérifie si on doit modifier la case, la case est définie avec le paramètre position qui s'agrémente de 1 à chaque fois
global test
global iteration
iteration = iteration+1
if position == 9*9:
return True
l = position//9
c = position%9
if grille[l][c] != 0:
return est_valide(grille , position+1)
else:
for k in range(1,10):
test = test+1
if absent_sur_ligne(k,grille,l) \
and absent_sur_colonne(k,grille,c) \
and absent_sur_bloc(k,grille,l,c):
grille[l][c] = k
if est_valide(grille,position+1):
return True
grille[l][c] = 0
return False
print("Grille avant\n") # C'est la partie du programme qui appelle les fonctions affichage et est_valide
affichage(grille_t)
est_valide(grille_t,0)
print("Grille apres\n")
affichage(grille_t)
print("\nNombre d'appels à la fonction est_valide : ")
print(iteration)
print("\nNombre de chiffres testés lors de la résolution : ")
print(test)
Grille avant 900 035 700 215 400 009 000 000 245 ------------------ 000 063 850 090 000 060 081 540 000 ------------------ 167 000 000 300 004 186 004 610 007 ------------------ Grille apres 946 235 718 215 487 639 738 196 245 ------------------ 472 963 851 593 871 462 681 542 973 ------------------ 167 328 594 329 754 186 854 619 327 ------------------ Nombre d'appels à la fonction est_valide : 208 Nombre de chiffres testés lors de la résolution : 1095
Pour une grille difficile, le nombre de chiffres testés est plutôt de l'ordre du million voire de la dizaine de millions, de même que le nombre d'appels à la fonction principale, est_valide. (Essayer d'appeler la fonction avec grille_d pour un exemple de grille difficile)
On récupère chaque chiffre en écriture manuscrite à partir de l'image fournie.
img = io.imread( "./digits.jpg", as_gray=True)
img.shape, img.min(), img.max()
((85, 366), 0.03529411764705882, 0.9495850980392156)
img[img > .6] = 1
xx = img.sum(axis = 0)
xx[ xx < 85] = 0
yy = img.sum(axis = 1)
yy[ yy < 366] = 0
y,x = img.shape
cx = np.convolve(xx, np.array([1,1,1]), mode = 'same' )
index = np.where(cx == 2*y)[0][1:-1]
strips = index.reshape((-1,2))
strips
array([[ 42, 57],
[ 85, 90],
[108, 129],
[143, 161],
[177, 200],
[210, 235],
[239, 256],
[271, 292],
[303, 327],
[335, 354]], dtype=int64)
cleaned = []
for strip in strips:
a,b = strip
im = img[:,a:b]
y,x = im.shape
index = np.where( im.sum(axis=1) < x )[0]
bottom, top = index.max(), index.min()
cleaned.append(img[top:bottom,a:b])
import pickle
with open("digits.pkl", "wb") as fp:
pickle.dump(cleaned, fp)
plt.imshow(cleaned[4])
<matplotlib.image.AxesImage at 0x1af0040dac0>
Avec chacun des chiffres en écriture manuscrite, on va créer une vignette carrée que l'on n'aura plus qu'à coller à la bonne place sur l'image.
def redim(im,c): # crée une vignette carrée (à la taille des cases de la grille) du chiffre avec l'écriture manuscrite
n, p = len(im), len(im[0])
ratio = p/n
case = np.zeros(shape=(c,c))+1.
if n>=p :
p_prime = int(c*ratio)
vignette = transform.resize(im, (c,p_prime))
marge = int((c-p_prime)/2)
case[:,marge:marge+p_prime] = vignette
else :
n_prime = int(c/ratio)
vignette = transform.resize(im, (n_prime,c))
marge = int((c-n_prime)/2)
case[marge:marge+n_prime,:] = vignette
return case
case_red = int(16/23*c)
chiffres = [redim(cleaned[i],case_red) for i in range(10)]
plt.imshow(chiffres[1])
<matplotlib.image.AxesImage at 0x1af0045e8e0>
fig, axs = plt.subplots(3, 3)
fig.set_size_inches(6,6)
axs = axs.ravel()
for ax in axs:
ax.set_axis_off()
for k, ax in zip(range(1,10),axs):
ax.imshow(chiffres[k]) ;
Ainsi tous les chiffres peuvent être traités de la même manière.
np.shape(chiffres[3])
(32, 32)
On implémente une fonction ecrit_chiffre qui remplace les pixels correspondant dans l'image de départ (ici appelée s) pour inscrire le chiffre donné en argument aux coordonnées indiquées.
def ecrit_chiffre(s,chiffre,coordonnées):
a,b = coordonnées
décalage = int((c - case_red)/2)
x = int(a*c + décalage)
y = int(b*c + décalage)
s[x:x+case_red, y:y+case_red] = 255*chiffres[chiffre]
#ecrit_chiffre(sudoku,2,(1,7))
#plt.imshow(sudoku)
def remplissage(image,solution):
for i in range(9):
for j in range(9):
k = solution[i][j]
if k!=0 and k!=grille_av[i][j]:
ecrit_chiffre(image,k,(i,j))
return image
im = Image.fromarray(remplissage(sudoku,grille_t))
im
im.save("Solution.jpg")
fig, axs = plt.subplots(1, 2)
fig.set_size_inches(10,10)
plt.subplot(121),plt.imshow(image_de_depart,cmap = 'gray')
plt.title('Sudoku non résolu'), plt.xticks([]), plt.yticks([])
plt.subplot(122),plt.imshow(im,cmap = 'gray')
plt.title('Sudoku résolu'), plt.xticks([]), plt.yticks([])
plt.show()
