Code source de ensae_teaching_cs.special.sudoku

"""
This file proposes a simple algorithm to solve a Sudoku. It finds the first possible solution.


:githublink:`%|py|5`
"""


[docs]def chiffre_barre_ligne(s, r, i): """ Look into every number in line *i*, if the number in column *k* ``s[i][k]`` is not null, :param s: current state of the sudoku :param r: array ``r[n] == 0`` means number *n+1* is already taken on this line :param i: line index (0 based) :githublink:`%|py|15` """ for k in range(0, 9): if s[i][k] > 0: r[s[i][k] - 1] = 0
[docs]def chiffre_barre_colonne(s, r, j): """ Look into every number in column *j*, if the number in column *k* ``s[i][k]`` is not null, :param s: current state of the sudoku :param r: array ``r[n] == 0`` means number *n+1* is already taken on this column :param j: column index (0 based) :githublink:`%|py|29` """ for k in range(0, 9): if s[k][j] > 0: r[s[k][j] - 1] = 0
[docs]def chiffre_barre_carre(s, r, i, j): """ Look into every number in sub square *i, j*, if a number in it ``s[i][k]`` is not null, :param s: current state of the sudoku :param r: array ``r[n] == 0`` means number *n+1* is already taken on this sub square :param i: sub square are indexed by :math:`(i, j) \\in \\{0, 1, 2\\}^2` (0 based) :param j: see parameter *i* :githublink:`%|py|44` """ a = i // 3 * 3 b = j // 3 * 3 for k in range(a, a + 3): for lb in range(b, b + 3): if s[k][lb] > 0: r[s[k][lb] - 1] = 0
[docs]def nombre_possible(s, i, j): """ tells for a particular position the list of possible number :param s: current state of the sudoku :param i: line index (0 based) :param j: column index (0 based) :return: 9-element array, 0: not possible, 1: possible at position *(i, j)* :githublink:`%|py|61` """ r = [1, 1, 1, 1, 1, 1, 1, 1, 1] chiffre_barre_ligne(s, r, i) chiffre_barre_colonne(s, r, j) chiffre_barre_carre(s, r, i, j) return r
[docs]def meilleure_case(s): """ look over all empty place and pick the one with the least possible options :param s: current state of the sudoku :return: *(i,j,r)*, *(i,j)* is the best position, *r* the list of possible numbers :githublink:`%|py|76` """ dmin = 10 imin = jmin = -1 rmin = [] for i in range(0, 9): for j in range(0, 9): if s[i][j] == 0: r = nombre_possible(s, i, j) d = sum(r) if d < dmin: dmin = d imin = i jmin = j rmin = r return imin, jmin, rmin
[docs]def resolution_sudoku(s): """ Solves the Sudoku. :param s: sudoku (0 for empty case) :return: 0 for impossible, 1 for possible, then *s* contains the solution The algorithm is the following: #. Find the position of a zero element (no number yet) with the smallest number of options #. If there is at least one possible option, try the first one, go to step 1 #. If not, the Sudoku cannot be solved, go back to last list of multiple options and try the next one. Example:: s = [[0, 0, 0, 3, 0, 0, 8, 0, 0], [0, 0, 7, 9, 0, 8, 0, 0, 5], [0, 0, 0, 2, 0, 4, 1, 0, 0], [0, 9, 0, 8, 1, 0, 0, 4, 7], [0, 4, 0, 0, 0, 0, 0, 0, 6], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 5, 0, 2, 0], [5, 3, 4, 0, 0, 0, 0, 0, 0], [0, 0, 0, 7, 0, 0, 0, 0, 0]] resolution_sudoku(s) for i in range(0, 9): print(s[i]) :githublink:`%|py|122` """ imin, jmin, rmin = meilleure_case(s) if imin == -1: return "jackpot" d = sum(rmin) if d == 1: p = rmin.index(1) s[imin][jmin] = p + 1 # s modifie ",imin,jmin,p+1 a = resolution_sudoku(s) if a == 0: s[imin][jmin] = 0 return 0 else: return 1 elif d == 0: # on s'arrete return 0 elif d > 1: # on continue for n in range(0, 9): if rmin[n] == 1: s[imin][jmin] = n + 1 a = resolution_sudoku(s) if a == 0: s[imin][jmin] = 0 else: return 1 return 0 else: raise RuntimeError("Should not happend.")
[docs]def sudoku2str(su): """ Converts a sudoku into a string. :param su: sudoku :return: string :githublink:`%|py|161` """ s = "" for i in range(0, len(su)): if i % 3 == 0: s += "-" * 35 s += "\n" for j in range(0, len(su[i])): if j % 3 == 0: s += " | " if su[i][j] > 0: s += str(su[i][j]) + " " else: s += "_ " s += " |\n" s += "-" * 35 s += "\n" return s