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)