Coverage for src/ensae_teaching_cs/special/sudoku.py: 99%
77 statements
« prev ^ index » next coverage.py v7.1.0, created at 2023-04-28 06:23 +0200
« prev ^ index » next coverage.py v7.1.0, created at 2023-04-28 06:23 +0200
1"""
2@file
3@brief This file proposes a simple algorithm to solve a Sudoku. It finds the first possible solution.
4"""
7def chiffre_barre_ligne(s, r, i):
8 """
9 Look into every number in line *i*,
10 if the number in column *k* ``s[i][k]`` is not null,
12 @param s current state of the sudoku
13 @param r array ``r[n] == 0`` means number *n+1* is already taken on this line
14 @param i line index (0 based)
15 """
16 for k in range(0, 9):
17 if s[i][k] > 0:
18 r[s[i][k] - 1] = 0
21def chiffre_barre_colonne(s, r, j):
22 """
23 Look into every number in column *j*,
24 if the number in column *k* ``s[i][k]`` is not null,
26 @param s current state of the sudoku
27 @param r array ``r[n] == 0`` means number *n+1* is already taken on this column
28 @param j column index (0 based)
29 """
30 for k in range(0, 9):
31 if s[k][j] > 0:
32 r[s[k][j] - 1] = 0
35def chiffre_barre_carre(s, r, i, j):
36 """
37 Look into every number in sub square *i, j*,
38 if a number in it ``s[i][k]`` is not null,
40 @param s current state of the sudoku
41 @param r array ``r[n] == 0`` means number *n+1* is already taken on this sub square
42 @param i sub square are indexed by :math:`(i, j) \\in \\{0, 1, 2\\}^2` (0 based)
43 @param j see parameter *i*
44 """
45 a = i // 3 * 3
46 b = j // 3 * 3
47 for k in range(a, a + 3):
48 for lb in range(b, b + 3):
49 if s[k][lb] > 0:
50 r[s[k][lb] - 1] = 0
53def nombre_possible(s, i, j):
54 """
55 tells for a particular position the list of possible number
57 @param s current state of the sudoku
58 @param i line index (0 based)
59 @param j column index (0 based)
60 @return 9-element array, 0: not possible, 1: possible at position *(i, j)*
61 """
62 r = [1, 1, 1, 1, 1, 1, 1, 1, 1]
63 chiffre_barre_ligne(s, r, i)
64 chiffre_barre_colonne(s, r, j)
65 chiffre_barre_carre(s, r, i, j)
66 return r
69def meilleure_case(s):
70 """
71 look over all empty place and pick the one with the least possible options
73 @param s current state of the sudoku
74 @return *(i,j,r)*, *(i,j)* is the best position,
75 *r* the list of possible numbers
76 """
77 dmin = 10
78 imin = jmin = -1
79 rmin = []
80 for i in range(0, 9):
81 for j in range(0, 9):
82 if s[i][j] == 0:
83 r = nombre_possible(s, i, j)
84 d = sum(r)
85 if d < dmin:
86 dmin = d
87 imin = i
88 jmin = j
89 rmin = r
90 return imin, jmin, rmin
93def resolution_sudoku(s):
94 """
95 Solves the Sudoku.
97 @param s sudoku (0 for empty case)
98 @return 0 for impossible, 1 for possible, then *s* contains the solution
100 The algorithm is the following:
102 #. Find the position of a zero element (no number yet) with the smallest number of options
103 #. If there is at least one possible option, try the first one, go to step 1
104 #. If not, the Sudoku cannot be solved, go back to last list of multiple options and try the next one.
106 Example::
108 s = [[0, 0, 0, 3, 0, 0, 8, 0, 0],
109 [0, 0, 7, 9, 0, 8, 0, 0, 5],
110 [0, 0, 0, 2, 0, 4, 1, 0, 0],
111 [0, 9, 0, 8, 1, 0, 0, 4, 7],
112 [0, 4, 0, 0, 0, 0, 0, 0, 6],
113 [0, 0, 0, 0, 0, 0, 0, 0, 0],
114 [0, 1, 0, 0, 0, 5, 0, 2, 0],
115 [5, 3, 4, 0, 0, 0, 0, 0, 0],
116 [0, 0, 0, 7, 0, 0, 0, 0, 0]]
118 resolution_sudoku(s)
120 for i in range(0, 9):
121 print(s[i])
122 """
123 imin, jmin, rmin = meilleure_case(s)
124 if imin == -1:
125 return "jackpot"
126 d = sum(rmin)
127 if d == 1:
128 p = rmin.index(1)
129 s[imin][jmin] = p + 1
130 # s modifie ",imin,jmin,p+1
131 a = resolution_sudoku(s)
132 if a == 0:
133 s[imin][jmin] = 0
134 return 0
135 else:
136 return 1
137 elif d == 0:
138 # on s'arrete
139 return 0
140 elif d > 1:
141 # on continue
142 for n in range(0, 9):
143 if rmin[n] == 1:
144 s[imin][jmin] = n + 1
145 a = resolution_sudoku(s)
146 if a == 0:
147 s[imin][jmin] = 0
148 else:
149 return 1
150 return 0
151 else:
152 raise RuntimeError("Should not happend.")
155def sudoku2str(su):
156 """
157 Converts a sudoku into a string.
159 @param su sudoku
160 @return string
161 """
162 s = ""
163 for i in range(0, len(su)):
164 if i % 3 == 0:
165 s += "-" * 35
166 s += "\n"
167 for j in range(0, len(su[i])):
168 if j % 3 == 0:
169 s += " | "
170 if su[i][j] > 0:
171 s += str(su[i][j]) + " "
172 else:
173 s += "_ "
174 s += " |\n"
175 s += "-" * 35
176 s += "\n"
177 return s