Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1# -*- coding: utf-8 -*- 

2""" 

3@file 

4@brief Fonctions, classes pour résoudre un puzzle à 9 pièces disposé en carré 3x3. Voir :ref:`l-puzzle_girafe`. 

5""" 

6 

7import time 

8import os 

9from pyquickhelper.loghelper import fLOG 

10from ..helpers.pygame_helper import wait_event, empty_main_loop 

11 

12 

13class PuzzleGirafeBord: 

14 """ 

15 Définition d'un bord ou côté d'une pièce, il possède : 

16 

17 - partie : une partie de la girafe (haut ou bas) 

18 - une couleur : la couleur de cette partie, (orange, violet, bleu clair, bleu foncé) 

19 """ 

20 

21 def __init__(self, definition): 

22 """ 

23 @param definition chaîne de caractères 

24 

25 *definition* est une chaîne de 2 caractères qui définit un bord, exemple : 

26 

27 * ``HO`` pour haut orange 

28 * ``BB`` pour bas bleu 

29 * ``BV`` pour bas violet 

30 * ``HM`` pour haut mauve 

31 """ 

32 

33 if definition[0] == "H": 

34 self.partie = "haut" 

35 elif definition[0] == "B": 

36 self.partie = "bas" 

37 else: 

38 self.partie = definition + "###" 

39 

40 if definition[1] == "O": 

41 self.couleur = "orange" 

42 elif definition[1] == "B": 

43 self.couleur = "bleu clair" 

44 elif definition[1] == "M": 

45 self.couleur = "violet" 

46 elif definition[1] == "V": 

47 self.couleur = "bleu fonce" 

48 else: 

49 self.couleur = definition + "##" 

50 

51 def __str__(self): 

52 """ 

53 Cette méthode est appelée lorsqu'on exécute l'instruction print 

54 avec un objet de type @see cl PuzzleGirafeBord. 

55 """ 

56 return self.partie + " " + self.couleur 

57 

58 def compatible(self, bord): 

59 """ 

60 dit si deux bords sont compatibles, c'est à dire 

61 de la même couleur et de partie différente 

62 """ 

63 return self.couleur == bord.couleur and self.partie != bord.partie 

64 

65 

66class PuzzleGirafePiece: 

67 """ 

68 Définition d'une pièce du puzzle, celle-ci inclut : 

69 

70 - **bord** : cette liste contient quatre objets de type Bord, cette liste ne changera plus 

71 - **position** : c'est la position de la pièce dans le puzzle, ce qui nous intéresse, 

72 c'est la position finale de la pièce dans le puzzle, cette information 

73 va donc bouger au fur et à mesure que nous allons essayer de 

74 résoudre le puzzle 

75 - **orientation** : de même que pour la position, une pièce peut être tournée sans changer de 

76 position, c'est le résultat final qui nous intèresse 

77 

78 pour l'affichage, on ajoute deux informations : 

79 

80 - **name** : le nom de l'image de la pièce 

81 - **image** : c'est la représentation de l'image dans la mèmoire de 

82 l'ordinateur pour le module pygame 

83 """ 

84 

85 def __init__(self, name, definition, position, numero): 

86 """ 

87 on définit la pièce 

88 

89 @param name nom de l'image représentant la pièce 

90 @param definition chaîne de 8 caractères, c'est une suite de 4 x 2 caractères définissant 

91 chaque bord, voir la classe bord pour leur signification 

92 @param position c'est la position initiale de la pièce, on suppose que 

93 l'orientation est nulle pour commencer 

94 @param numero numéro de la pièce 

95 

96 à partir de ces informations, on construit : 

97 

98 - **image** : c'est la représentation en mémoire de l'image de la pièce 

99 - **bord** : c'est une liste qui définit les 4 bords de la pièce 

100 - **orientation** : c'est l'orientation de la pièce, au début de la résolution, elle est nulle 

101 """ 

102 self.name = name 

103 self.bord = [] 

104 

105 for i in range(0, 4): 

106 self.bord.append(PuzzleGirafeBord(definition[i * 2:i * 2 + 2])) 

107 

108 self.orientation = 0 

109 self.position = position 

110 self.numero = numero 

111 

112 def load_image(self, pygame): 

113 """ 

114 charge l'image pour une simulation graphique 

115 

116 @param pygame module :epkg:`pygame` 

117 """ 

118 image = pygame.image.load(self.name) 

119 self.image = pygame.transform.scale(image, (250, 250)) 

120 s = self.image.get_size() 

121 self.image_petite = pygame.transform.scale( 

122 self.image, (int(s[0] * 0.7), int(s[1] * 0.7))) 

123 

124 def __str__(self): 

125 """ 

126 définition ce qu'on doit afficher lorsqu'on exécute 

127 l'instruction print avec un objet de type @see cl PuzzleGirafePiece. 

128 """ 

129 s = str(self.position) + " : " 

130 for b in self.bord: 

131 s += str(b) + " - " 

132 s += " orientation " + str(self.orientation) 

133 s += " numero " + str(self.numero) 

134 return s 

135 

136 def bord_angle(self, angle, orientation=None): 

137 """ 

138 retourne le bord connaissant l'orientation de la pièce, 

139 le bord demandé est celui correspondant à : 

140 

141 - 0 bord droit 

142 - 90 bord haut 

143 - 180 bord gauche 

144 - 270 bord bas 

145 """ 

146 if orientation is None: 

147 return self.bord_angle(angle, self.orientation) 

148 else: 

149 dif = (angle - orientation + 360) % 360 // 90 

150 return self.bord[dif] 

151 

152 def voisin_possible(self, p, a): 

153 """ 

154 détermine si la pièce *self* peut être voisine avec la pièce *p* tournée de l'angle *a* 

155 """ 

156 d = p.position - self.position 

157 if abs(d) == 1 and (p.position - 1) // 3 == (self.position - 1) // 3: 

158 # voisin en x 

159 if d == 1: 

160 a1 = 0 

161 a2 = a1 + 180 

162 else: 

163 a1 = 180 

164 a2 = 0 

165 elif abs(d) == 3: 

166 # voisin en y 

167 if d == 1: 

168 a1 = 90 

169 a2 = 270 

170 else: 

171 a1 = 270 

172 a2 = 90 

173 else: 

174 # pas voisin 

175 return False 

176 

177 b1 = self.bord_angle(a1) 

178 b2 = p.bord_angle(a2, a) 

179 return b1.compatible(b2) 

180 

181 

182class PuzzleGirafe: 

183 """ 

184 définition d'une classe puzzle, elle contient simplement 

185 une liste de 9 pièces dont les positions sont :: 

186 

187 1 2 3 

188 4 5 6 

189 7 8 9 

190 

191 et les orientations choisies dans l'ensemble *{ 0,90,180,270 }* 

192 

193 Voir :ref:`l-puzzle_girafe`. 

194 """ 

195 

196 def __init__(self): 

197 """ 

198 on définit le puzzle à partir des informations contenues 

199 dans le répertoire *data* de ce module qui doit contenir : 

200 

201 - 9 images appelées ``piece1.png``, ..., ``piece0.png`` 

202 - un fichier ``definition_puzzle_girafe.txt`` contenant la définition de 

203 chacun des 4 bords de chacune des 9 pièces:: 

204 

205 HOBBBVHM 

206 HOBBBVHM 

207 HBBMBVHO 

208 HMBBBVHB 

209 BMBOHBHV 

210 HVBMBOHM 

211 BMBVHBHO 

212 HVHMBBBO 

213 BMHOHVBB 

214 """ 

215 dir_ = os.path.abspath(os.path.dirname(__file__)) 

216 dir_ = os.path.join(dir_, "data") 

217 

218 with open(os.path.join(dir_, "definition_puzzle_girafe.txt"), "r") as f: 

219 bo = f.readlines() 

220 

221 # on définit chaque pièce 

222 self.piece = [] 

223 for i in range(1, 10): 

224 name = os.path.join(dir_, "piece%d.png" % i) 

225 d = bo[i - 1] 

226 p = PuzzleGirafePiece(name, d, 0, i) 

227 self.piece.append(p) 

228 

229 def load_images(self, pygame): 

230 """ 

231 charge les images pour une simulation graphique 

232 

233 @param pygame module :epkg:`pygame` 

234 """ 

235 for p in self.piece: 

236 p.load_image(pygame) 

237 

238 def __str__(self): 

239 """ 

240 ce qu'on doit afficher lorsqu'on exécute 

241 l'instruction print avec un objet de type @see cl PuzzleGirafe. 

242 """ 

243 s = """1 2 3 

244 4 5 6 

245 7 8 9 

246 """.replace(" ", "") 

247 for p in self.piece: 

248 s += str(p) + "\n" 

249 return s 

250 

251 def pixel(self, position): 

252 """ 

253 retourne en fonction de la position (1 à 9) de la pièce sa position sur l'écran, 

254 soit deux coordonnées 

255 

256 @return tuple *(x,y)* 

257 """ 

258 p = position - 1 

259 ligne = p // 3 

260 colonne = p % 3 

261 return (colonne * 250, ligne * 250) 

262 

263 def meilleure_piece(self, free, pos): 

264 """ 

265 retourne la prochaine pièce à placer sur le puzzle, 

266 dans un premier temps, on peut prend la première qui vient, 

267 ensuite, on peut essayer un choix plus judicieux 

268 """ 

269 if len(free) == 0: 

270 return None 

271 else: 

272 return free[0] 

273 

274 def piece_position(self, pi): 

275 """ 

276 recherche la piece associée à la position pi 

277 """ 

278 for p in self.piece: 

279 if p.position == pi: 

280 return p 

281 return None 

282 

283 def ensemble_voisin(self, i): 

284 """ 

285 retourne les positions voisins de la position i 

286 """ 

287 i -= 1 

288 res = [] 

289 for x in [-1, 0, 1]: 

290 for y in [-1, 0, 1]: 

291 if abs(x) == abs(y): 

292 continue 

293 if x == -1 and i % 3 == 0: 

294 continue 

295 if x == 1 and i % 3 == 2: 

296 continue 

297 if y == -1 and i // 3 == 0: 

298 continue 

299 if y == 1 and i // 3 == 2: 

300 continue 

301 j = i + x + y * 3 

302 if j in range(0, 9): 

303 res.append(j) 

304 return [j + 1 for j in res] 

305 

306 def nb_place(self): 

307 """ 

308 retourne le nombre de places vides 

309 """ 

310 i = 0 

311 for p in self.piece: 

312 if p.position == 0: 

313 i += 1 

314 return i 

315 

316 def angle_possible(self, p, display=False): 

317 """ 

318 retourne l'ensemble des angles possibles pour une pièce donnée 

319 """ 

320 voisin = self.ensemble_voisin(p.position) 

321 if display: 

322 print("voisin = ", voisin) 

323 res = [] 

324 for a in [0, 90, 180, 270]: 

325 r = True 

326 for v in voisin: 

327 piece = self.piece_position(v) 

328 if piece is not None: 

329 r = r and piece.voisin_possible(p, a) 

330 if r: 

331 res.append(a) 

332 return res 

333 

334 def solution(self, pos=1, screen=None, pygame=None, images=None, delay=200): 

335 """ 

336 Résoud le puzzle de façon récursive : on pose une pièce puis on résoud 

337 le puzzle restant (une pièce en moins, une case en moins). 

338 

339 @param pos niveau de récursivité 

340 @param screen image pygame 

341 @param pygame module pygame 

342 @param images stores images in this list if not None 

343 @param delay delay between two tries 

344 

345 L'affichage *pygame* est optionnel. 

346 """ 

347 if pos == 1: 

348 for p in self.piece: 

349 p.position = 0 

350 self.nb_position = 0 

351 self.essai = 0 

352 

353 self.essai += 1 

354 

355 if self.nb_position == len(self.piece): 

356 time.sleep(0.2) 

357 return None 

358 

359 # le tableau free mémorise l'ensemble des pièces non encore placées 

360 free = [] 

361 for p in self.piece: 

362 if p.position == 0: 

363 free.append(p) 

364 

365 if screen is not None and pygame is not None and images is not None: 

366 empty_main_loop(pygame) 

367 display_puzzle_girafe(self, screen, True, pygame=pygame) 

368 pygame.display.flip() 

369 images.append(screen.copy()) 

370 

371 p = self.meilleure_piece(free, pos) 

372 # si p == None, on n'étudie pas les solutions avec les pièces placées 

373 # avant aux positions 1 à pos --> on n'entrera pas dans la boucle 

374 # suivante 

375 while p is not None: 

376 

377 p.position = pos 

378 angle = self.angle_possible(p) 

379 

380 # p est la pièce choisie, pour cette pièce 

381 # on passe en revue toutes les orientations 

382 for a in angle: 

383 p.orientation = a 

384 

385 if pygame is not None: 

386 pygame.time.wait(delay) 

387 

388 if self.nb_place() == 0: 

389 return True 

390 else: 

391 r = self.solution(pos + 1, screen=screen, 

392 pygame=pygame, images=images, delay=delay) 

393 if r: 

394 return True 

395 

396 p.position = 0 

397 

398 # on réactualise le tableau free qui aura été modifié par 

399 # l'appel à self.solution et on enlève le choix précédemment 

400 # testé 

401 free2 = free 

402 free = [] 

403 for f in free2: 

404 if f.numero != p.numero: 

405 free.append(f) 

406 

407 # on passe au choix suivant avec free contenant les pièces 

408 # placées et les pièces essayées 

409 p = self.meilleure_piece(free, pos) 

410 return None 

411 

412 

413def display_puzzle_girafe(self, screen, petite=False, pygame=None): 

414 """ 

415 affiche les pièces sur l'écran, 

416 en plus petit pour celles qui ne sont pas encore placées 

417 """ 

418 screen.fill((0, 0, 0)) 

419 free = [0 for i in self.piece] 

420 for p in self.piece: 

421 if p.position > 0: 

422 p.darker = False 

423 display_puzzle_girafe_piece( 

424 p, screen, self.pixel(p.position), pygame=pygame) 

425 free[p.position - 1] = 1 

426 

427 if petite: 

428 em = [] 

429 for i in range(0, len(free)): 

430 if free[i] == 0: 

431 em.append(i + 1) 

432 i = 0 

433 for p in self.piece: 

434 if p.position == 0: 

435 p.darker = True 

436 display_puzzle_girafe_piece( 

437 p, screen, self.pixel(em[i]), pygame) 

438 i += 1 

439 

440 pygame.display.flip() 

441 

442 

443def display_puzzle_girafe_piece(self, screen, position, pygame): 

444 """ 

445 affiche la pièce en tenant compte de sa position et de son orientation 

446 """ 

447 if "darker" in self.__dict__ and self.darker: 

448 position = (position[0] + 20, position[1] + 20) 

449 image = pygame.transform.rotate(self.image_petite, self.orientation) 

450 screen.blit(image, position) 

451 else: 

452 image = pygame.transform.rotate(self.image, self.orientation) 

453 screen.blit(image, position) 

454 

455 

456def pygame_simulation(pygame, first_click=False, folder=None, 

457 size=(750, 750), fLOG=fLOG, delay=200, 

458 flags=0): 

459 """ 

460 Simulation graphique. 

461 Illuste la résolution du puzzle 

462 

463 @param pygame module pygame 

464 @param first_click attend la pression d'un clic de souris avant de commencer 

465 @param folder répertoire où stocker les images de la simulation 

466 @param size taille de l'écran 

467 @param delay delay between two tries 

468 @param flags see `pygame.display.set_mode <https://www.pygame.org/docs/ref/display.html#pygame.display.set_mode>`_ 

469 @param fLOG logging function 

470 @return @see cl PuzzleGirafe 

471 

472 La simulation ressemble à ceci : 

473 

474 .. raw:: html 

475 

476 <video autoplay="" controls="" loop="" height="500"> 

477 <source src="http://www.xavierdupre.fr/enseignement/complements/puzzle_girafe.mp4" type="video/mp4" /> 

478 </video> 

479 

480 Pour lancer la simulation:: 

481 

482 from ensae_teaching_cs.special.puzzle_girafe import pygame_simulation 

483 import pygame 

484 pygame_simulation(pygame) 

485 

486 Voir :ref:`l-puzzle_girafe`. 

487 """ 

488 # initialisation du module pygame 

489 pygame.init() 

490 screen = pygame.display.set_mode(size, flags) 

491 

492 # on définit le puzzle 

493 p = PuzzleGirafe() 

494 p.load_images(pygame) 

495 

496 # on affiche le puzzle avec print (format texte) 

497 fLOG("\n" + str(p)) 

498 

499 # on affiche le puzzle à l'écran 

500 display_puzzle_girafe(p, screen, petite=True, pygame=pygame) 

501 if first_click: 

502 wait_event(pygame) 

503 

504 # on rafraîchit l'écran pour que le puzzle apparaissent 

505 pygame.display.flip() 

506 

507 images = [] if folder is not None else None 

508 

509 # on trouve la solution 

510 r = p.solution(screen=screen, pygame=pygame, images=images, delay=delay) 

511 fLOG("résolution ", r) 

512 fLOG("nombre d'appels à la méthode solution ", p.essai) 

513 

514 if images is not None: 

515 empty_main_loop(pygame) 

516 display_puzzle_girafe(p, screen, True, pygame=pygame) 

517 pygame.display.flip() 

518 images.append(screen.copy()) 

519 

520 if folder is not None: 

521 fLOG("saving images") 

522 for it, screen in enumerate(images): 

523 if it % 10 == 0: 

524 fLOG("saving image:", it) 

525 image = os.path.join(folder, "image_%04d.png" % it) 

526 pygame.image.save(screen, image) 

527 

528 # on attend la pression d'un clic de souris avant de terminer le programme 

529 display_puzzle_girafe(p, screen, petite=True, pygame=pygame) 

530 if first_click: 

531 wait_event(pygame)