# sudoto.py

Created by andreanx

Created on December 06, 2023

7.08 KB

Sudoku solver
Usage : sudoto(grid, show, steps) where :
grid = sudoto grid (examples are included : g0, g1, g2 and g3)
show = True for graphic display
steps = True to show steps on graphic display

```from kandinsky import *

L_FENETRE, H_FENETRE = 320, 212
POLICE_INFOS = (10,18,1,1) # caracteres numeriques des polices : largeur utile + hauteur utile + marge gauche + marge haute
L_CASE = min((L_FENETRE - 4) // 9, (H_FENETRE - 4) // 9)

def hsv2rgb(h, s=1, v=1):
h *= 6
c = v * s
x = c * (1 - abs((h % 2) - 1))
r, g, b = h < 1 and (c, x, 0) or h < 2 and (x, c, 0) or h < 3 and (0, c, x) or h < 4 and (0, x, c) or h < 5 and (x, 0, c) or (c, 0, x)
return [int((k + v - c) * 255) for k in (r, g, b)]

def draw_vert(x, y1, y2, c):
for y in range(y1, y2): set_pixel(x, y, c)

def draw_horiz(x1, x2, y, c):
for x in range(x1, x2): set_pixel(x, y, c)

def fill_rect(x, y, l, h, c):
for dy in range(h):
for dx in range(l): set_pixel(x + dx, y + dy, c)

def x_col(c, text=False): return POLICE_INFOS[2] + c*L_CASE + c//3 + (text and 1 + (L_CASE - 1 - POLICE_INFOS[0])//2 - POLICE_INFOS[2])
def y_line(l, text=False): return POLICE_INFOS[3] + l*L_CASE + l//3 + (text and 1 + (L_CASE - 1 - POLICE_INFOS[1])//2 - POLICE_INFOS[3])

def clear_case(l, c, back=(255,255,255)):
x, y = x_col(c) + 1, y_line(l) + 1
fill_rect(x, y, L_CASE - 1, L_CASE - 1, back)

def draw_case(grille, l, c, col, back=(255,255,255)):
x, y = x_col(c) + 1, y_line(l) + 1
if back: clear_case(l, c, back)
draw_string(str(grille[l][c][0]), x_col(c, True), y_line(l, True), col, back and back or get_pixel(x, y))

def clear_grille(grille):
for l in range(9):
for c in range(9):
if len(grille[l][c]) != 1:
clear_case(l, c)

def redraw_grille(grille_back, grille, refresh=True):
for l in range(9):
for c in range(9):
if len(grille[l][c]) == 1:
draw_case(grille, l, c, COLORS[grille[l][c][0]], len(grille_back[l][c]) == 1 and (191, 191, 191) or (255, 255, 255))

def draw_grille(grille_back, grille, refresh=True):
for l in range(10):
for c in range(10):
for i in range(c % 3 == 0 and -1, 1): draw_vert(x_col(c) + i, y_line(0), y_line(9), COLORS[0])
for i in range(l % 3 == 0 and -1, 1): draw_horiz(x_col(0), x_col(9), y_line(l) + i, COLORS[0])
redraw_grille(grille_back, grille, refresh)

def ligne(grille, l): return [(l, c) for c in range(9)]
def colonne(grille, c): return [(l, c) for l in range(9)]

def carre(grille, l, c):
lst = []
for l2 in range(l - (l % 3), l + 3 - (l % 3)): lst.extend([(l2, c2) for c2 in range(c - (c % 3), c + 3 - (c % 3))])
return lst

def lst_inclus(l1, l2):
for v in l1:
if not(v in l2): return False
return True

def rechercher_exclusifs(grille, l, c, secteur):
lc = []
for (l2, c2) in secteur:
if lst_inclus(grille[l2][c2], grille[l][c]):
lc.append((l2, c2))
if len(lc) == len(grille[l][c]): break
return lc

def grille_copy(grille): return [[v.copy() for v in l] for l in grille]

def list_grille(grille):
for l in range(9):
for c in range(9): grille[l][c] = grille[l][c] == 0 and list(range(1, 10)) or [grille[l][c]]
return grille

def unlist_grille(grille):
for l in range(9):
for c in range(9):
if len(grille[l][c]) == 1: grille[l][c] = grille[l][c][0]
return grille

def sudo_remplir(grille, a_tester, show = True):
global cpt
lmin, cmin = a_tester[0]
a_explorer = [lmin, cmin]
lenmin = 9
while len(a_tester):
l, c = a_tester[0]
a_tester.pop(0)
if len(grille[l][c]) < 9:
for secteur in (colonne(grille, c), ligne(grille, l), carre(grille, l, c)):
# recherche dans le secteur des cases permet de constituer une exclusivite (paires exclusives, triplets exclusifs, etc.)
lst = rechercher_exclusifs(grille, l, c, secteur)
if len(lst) == len(grille[l][c]):
# exclusion des valeurs des autres cases du secteur
for (l2, c2) in secteur:
if not((l2, c2) in lst):
t = False
for vi in grille[l][c]:
if vi in grille[l2][c2]:
grille[l2][c2].remove(vi)
if (l2, c2) in a_explorer:
a_explorer.remove((l2, c2))
t = True
if t:
if len(grille[l2][c2]) == 1 and show: draw_case(grille, l2, c2, COLORS[grille[l2][c2][0]])
cpt[0] += 1
if len(grille[l2][c2]) and not ((l2, c2) in a_tester):
a_tester.append((l2, c2))
if len(grille[l2][c2]) != 1 and len(grille[l2][c2]) <= lenmin:
if len(grille[l2][c2]) < lenmin:
a_explorer = []
lmin, cmin, lenmin = l2, c2, len(grille[l2][c2])
if not (l2, c2) in a_explorer:
a_explorer.append((l2, c2))
if len(grille[l2][c2]) == 0: break
if lenmin == 0: break
return len(a_explorer) and a_explorer[0] or (lmin, cmin)

COLORS = [(0,0,0)]
COLORS.extend([hsv2rgb(h / 10, 1, 1) for h in range(10)])

def sudoto_rec(grille_back, grille, a_tester, show = True):
global cpt
l, c = sudo_remplir(grille, a_tester, show)
lastlen = len(grille[l][c])
if lastlen <= 1:
return lastlen == 1
else:
if show: draw_grille(grille_back, grille, False)
for v in grille[l][c]:
grille_copie = grille_copy(grille)
grille_copie[l][c] = [v]
cpt[1] += 1
if show: draw_case(grille_copie, l, c, COLORS[v], (0, 0, 0))
t = sudoto_rec(grille_back, grille_copie, [(l, c)], show)
if t:
for l in range(9): grille[l] = grille_copie[l]
return True
if show: clear_case(l, c)
return False

def sudoto(grille, show = True, steps = True):
global cpt
cpt = [0, 0]
grille = list_grille(grille)
grille_back = grille_copy(grille)
if show: draw_grille(grille_back, grille)
a_tester = []
for l in range(9):
for c in range(9):
if len(grille[l][c]) < 9: a_tester.append((l, c))
t = sudoto_rec(grille_back, grille, a_tester, show and steps)
if show and not steps: draw_grille(grille_back, grille, False)
grille = unlist_grille(grille)
print((t and "succes" or "echec") + "\n{:d} etape{:s} dont :\n  {:d} deduction{:s}\n  {:d} pari{:s}".format(cpt[0] + cpt[1], cpt[0] + cpt[1] > 1 and "s" or "", cpt[0], cpt[0] > 1 and "s" or "", cpt[1], cpt[1] > 1 and "s" or ""))
for l in range(9): print(grille[l])

g1=[[0,1,6,7,8,0,3,0,0], # Casio Paques 1
[0,0,7,0,4,0,9,6,8],
[0,0,0,0,2,6,1,0,0],
[6,2,0,0,7,0,0,3,0],
[0,7,0,0,5,0,0,9,0],
[0,5,0,0,9,0,0,7,1],
[0,0,5,2,3,0,0,0,0],
[1,4,2,0,6,0,7,0,0],
[0,0,3,0,1,4,2,8,0]]
g2=[[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]]
g0=[[1,0,0,0,0,7,0,9,0], # Al Escargot
[0,3,0,0,2,0,0,0,8],
[0,0,9,6,0,0,5,0,0],
[0,0,5,3,0,0,9,0,0],
[0,1,0,0,8,0,0,0,2],
[6,0,0,0,0,4,0,0,0],
[3,0,0,0,0,0,0,1,0],
[0,4,0,0,0,0,0,0,7],
[0,0,7,0,0,0,3,0,0]]
g3=[[8,0,0,0,0,0,0,0,0], # NumWorks Decembre 2023
[0,0,3,6,0,0,0,0,0],
[0,7,0,0,9,0,2,0,0],
[0,5,0,0,0,7,0,0,0],
[0,0,0,0,4,5,7,0,0],
[0,0,0,1,0,0,0,3,0],
[0,0,1,0,0,0,0,6,8],
[0,0,8,5,0,0,0,1,0],
[0,9,0,0,0,0,4,0,0]]
sudoto(g2, True, True)```