# Coverage for src/ensae_teaching_cs/special/sudoku.py: 99%

## 77 statements

, created at 2023-01-27 05:44 +0100

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