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

1""" 

2@file 

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

4""" 

5 

6 

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, 

11 

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 

19 

20 

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, 

25 

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 

33 

34 

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, 

39 

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 

51 

52 

53def nombre_possible(s, i, j): 

54 """ 

55 tells for a particular position the list of possible number 

56 

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 

67 

68 

69def meilleure_case(s): 

70 """ 

71 look over all empty place and pick the one with the least possible options 

72 

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 

91 

92 

93def resolution_sudoku(s): 

94 """ 

95 Solves the Sudoku. 

96 

97 @param s sudoku (0 for empty case) 

98 @return 0 for impossible, 1 for possible, then *s* contains the solution 

99 

100 The algorithm is the following: 

101 

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. 

105 

106 Example:: 

107 

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]] 

117 

118 resolution_sudoku(s) 

119 

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.") 

153 

154 

155def sudoku2str(su): 

156 """ 

157 Converts a sudoku into a string. 

158 

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