# ========================================================================================= # Problème de logique : Qui possède un éléphant ? # Résolution du problème par force brute # Version 1 : teste 16 millions de tableaux en 4 minutes environ # Pour cela on a préremplit 5 cases dans le tableau # nsi.gecif.net # Janvier 2026 # ========================================================================================= """ L'énoncé du problème est le suivant : Cinq personnes de professions et de prénoms différents habitent des maisons de couleurs différentes et situées côte à côte dans le même alignement. Ils jouent chacun d'un instrument de musique particulier et ont chacun un animal. Les données du problème sont : 1. la maison où il y a un hamster est à côté de celle du pâtissier 2. le propriétaire de la maison du milieu joue de l'harmonica 3. Gaspard est voiturier 4. le banquier élève un coq 5. le propriétaire de la maison bleue est Gilbert 6. Simon habite à côté de la maison jaune 7. la maison où il y a un panda est à côté de celle du musicien 8. dans sa maison le vigile joue de la mandoline 9. Maxime a un lion 10. Alexis joue du violoncelle 11. c'est de la trompette que le propriétaire de la maison rose joue 12. la maison violette est immédiatement à gauche de la maison rose 13. le pâtissier habite la maison rouge 14. il n'y a pas de voisin à gauche de la maison de Simon La problématique à résoudre est : Qui joue du xylophone et qui possède un éléphant ? ###################################################################################################### ATTENTION : tout ce qui est dans le programme ci-dessous correspond au problème « Qui possède un pingouin ? » Le travail à faire est de modifier tout le programme (code source Python + les commentaires) pour l'adapter à ce nouveau problème « Qui possède un éléphant ? » ###################################################################################################### """ from itertools import * # ############################################################################################## # Fonction solution() # ############################################################################################## def solution(tableau): # la fonction solution compare le tableau passé en paramètre à l'énnoncé du problème : # elle renvoie True si le tableau correspond en tout point à la problématique, False dans le cas contraire """ En décortiquant l'énoncé on obtient 3 cases pleines définitivemant dans le tableau, une condition qui n'a que 2 possibilités et 10 conditions restantes : Les 3 certitudes sont : 8. il n'y a pas de voisin à gauche de la maison du Chilien : maison 1 -> Chilien 5. le Chilien habite à côté de la maison marron : maison 2 -> marron 11. dans la maison du milieu on joue du xylophone : maison 3 -> xylophone La condition qui n'a que 2 solutions (à tester séparément) est : 7. la maison blanche est immédiatement à droite de la maison noire -> on sait que la maison 2 est marron donc : -> soit maison 3 -> noire et maison 4 -> blanche -> soit maison 4 -> noire et maison 5 -> blanche -> il suffit d'imposer un de ces 2 cas pour remplir les 4ème et 5ème cases du tableau Les 10 conditions que Python doit tester par force brute sont (sachant qu'il a déjà 5 cases pleines dans le tableau) : 8 relations simples (lien direct entre 2 attributs) : 2. le traiteur habite la maison grise 3. le Japonais joue de la contrebasse 4. la profession de l'Irlandais est coiffeur 6. dans la maison blanche on joue du hautbois 10. le propriétaire de la maison rouge est le Grec 12. le charpentier élève une autruche 13. le restaurateur joue de la guitare 14. il y a un coq dans la maison du Français 2 relations doubles (relations de voisinage) : 1. le chanteur habite une maison voisine de celle où il y a un caméléon 9. le traiteur habite une maison voisine de celle où il y a un hippopotame """ # ########################################################### # 8 conditions avec une seule boucle (donc rapide à tester) : # ########################################################### # ========================================================================================= # CONDITION 2 : # 2. le traiteur habite la maison grise for i in range(1,6): if tableau[i]['profession']=='traiteur' and tableau[i]['couleur']!='grise': return False # ========================================================================================= # CONDITION 3 : # 3. le Japonais joue de la contrebasse for i in range(1,6): if tableau[i]['nationalité']=='Japonais' and tableau[i]['instrument']!='contrebasse': return False # ========================================================================================= # CONDITION 4 : # 4. la profession de l'Irlandais est coiffeur for i in range(1,6): if tableau[i]['nationalité']=='Irlandais' and tableau[i]['profession']!='coiffeur': return False # ========================================================================================= # CONDITION 6 : # 6. dans la maison blanche on joue du hautbois for i in range(1,6): if tableau[i]['couleur']=='blanche' and tableau[i]['instrument']!='hautbois': return False # ========================================================================================= # CONDITION 10 : # 10. le propriétaire de la maison rouge est le Grec for i in range(1,6): if tableau[i]['nationalité']=='Grec' and tableau[i]['couleur']!='rouge': return False # ========================================================================================= # CONDITION 12 : # 12. le charpentier élève une autruche for i in range(1,6): if tableau[i]['profession']=='charpentier' and tableau[i]['animal']!='autruche': return False # ========================================================================================= # CONDITION 13 : # 13. le restaurateur joue de la guitare for i in range(1,6): if tableau[i]['profession']=='restaurateur' and tableau[i]['instrument']!='guitare': return False # ========================================================================================= # CONDITION 14 : # 14. il y a un coq dans la maison du Français for i in range(1,6): if tableau[i]['nationalité']=='Français' and tableau[i]['animal']!='coq': return False # ########################################################### # 2 conditions avec 2 boucles (donc plus lente à tester) : # ########################################################### # ========================================================================================= # CONDITION 1 : # 1. le chanteur habite une maison voisine de celle où il y a un caméléon # cherchons la position de la maison du chanteur : for i in range(1,6): if tableau[i]['profession']=='chanteur': position_chanteur=i # cherchons la position de la maison du caméléon : for i in range(1,6): if tableau[i]['animal']=='caméléon': position_cameleon=i if abs(position_chanteur-position_cameleon)!=1 : return False # ========================================================================================= # CONDITION 9 : # 9. le traiteur habite une maison voisine de celle où il y a un hippopotame # cherchons la position de la maison du traiteur : for i in range(1,6): if tableau[i]['profession']=='traiteur': position_traiteur=i # cherchons la position de la maison de l'hippopotame : for i in range(1,6): if tableau[i]['animal']=='hippopotame': position_hippopotame=i if abs(position_traiteur-position_hippopotame)!=1 : return False # On retourne True si on a "échapé" aux tests précédents, c'est-à-dire si les 11 conditions sont vérifiées : return True # ############################################################################################## # Programme principal # ############################################################################################## # la structure de données utilisée ici est une liste de dictionnaires : # - les 5 maisons sont dans une liste à 6 éléments dont seuls les éléments 1 à 5 sont utilisés # - la liste permet d'avoir la notion d'ordre # - la liste contient 5 dictionnaires dont les 5 clés sont nationalité, profession, couleur, animal et instrument # on crée la liste contenant 5 dictionnaires vides pour l'instant : # liste_maisons[0] n'est pas utilisé et vaut None # maison 1 : liste_maisons[1] (maison de gauche) # maison 2 : liste_maisons[2] # maison 3 : liste_maisons[3] # maison 4 : liste_maisons[4] # maison 5 : liste_maisons[5] (maison de droite) """ Les 3 certitudes sont : 8. il n'y a pas de voisin à gauche de la maison du Chilien : maison 1 -> Chilien 5. le Chilien habite à côté de la maison marron : maison 2 -> marron 11. dans la maison du milieu on joue du xylophone : maison 3 -> xylophone L'idée est alors de remplir directement ces 3 cases dans tous les tableaux qu'on teste Et pour accélérer le programme on lui remplit 2 cases suplémentaires : 7. la maison blanche est immédiatement à droite de la maison noire -> soit maison 3 -> noire et maison 4 -> blanche -> soit maison 4 -> noire et maison 5 -> blanche Il reste : 4 nationalités à tester : 4!=24 cas différents 5 professions à tester : 5!=120 cas différents 2 couleurs à tester : 2!=2 cas différents 5 animaux à tester : 5!=120 cas différents 4 instrument à tester : 4!=24 cas différents Il ne reste alors plus que 24*120*2*120*24=16588800 tableaux différents à tester par force brute : De 24883200000 (120**5 soit 24 milliards) tableaux différents on passe à 16588800 (16 millions) tableaux différents à tester (soit 1500 fois moins) """ liste_maisons=[None,\ {'nationalité':None,'profession':None,'couleur':None,'animal':None,'instrument':None},\ {'nationalité':None,'profession':None,'couleur':None,'animal':None,'instrument':None},\ {'nationalité':None,'profession':None,'couleur':None,'animal':None,'instrument':None},\ {'nationalité':None,'profession':None,'couleur':None,'animal':None,'instrument':None},\ {'nationalité':None,'profession':None,'couleur':None,'animal':None,'instrument':None}] # liste des 4 nationalités (en plus de 'Chilien' dans la maison 1) sous forme de tuple : liste_nationalite=('Japonais','Irlandais','Grec','Français') # liste des 5 professions sous forme de tuple : liste_profession=('chanteur','traiteur','coiffeur','charpentier','restaurateur') # liste des 2 couleurs (en plus de 'marron' dans la maison 2 et de 'blanche' et 'noire' qui seront insérées dans le tableau) sous forme de tuple : liste_couleur=('grise','rouge') # liste des 5 animaux sous forme de tuple : liste_animal=('caméléon','hippopotame','autruche','coq','pingouin') # liste des 4 instruments de musique (en plus de 'xylophone' dans la maison 3) sous forme de tuple : liste_instrument=('contrebasse','hautbois','guitare','clarinette') tous_les_cas_nationalite=tuple(permutations(liste_nationalite)) tous_les_cas_profession=tuple(permutations(liste_profession)) tous_les_cas_couleur=tuple(permutations(liste_couleur)) tous_les_cas_animal=tuple(permutations(liste_animal)) tous_les_cas_instrument=tuple(permutations(liste_instrument)) solutions_testees=0 solutions_trouvees=0 progression=1 # Si le programme doit remplir un tableau vide : # 120**5 = 24883200000 = 24 883 200 000 = 24 milliards d'itérations soit 24 milliards de tableaux à tester : il faut 120 heures (5 jours) # Si on donne comme ici 5 cases remplies dans le tableau (une case par ligne) : # 24*120*2*120*24 = 16588800 = 16 millions d'itérations soit 16 millions de tableaux à tester : il faut environ 4 minutes for t_nationalite in tous_les_cas_nationalite: # boucle 24 fois # on ajoute à la main la 5ème nationalité ('Chilien') dans la maison 1 : t_nationalite=('Chilien',)+t_nationalite for t_couleur in tous_les_cas_couleur: # boucle 2 fois # on ajoute à la main la couleur 'marron' dans la maison 2, et les couluers 'noire' et 'blanche' : il y a 2 cas à tester # CAS 1 : maison 3 -> noire et maison 4 -> blanche t_couleur=(t_couleur[0],)+('marron',)+('noire','blanche')+(t_couleur[1],) # CAS 2 : maison 4 -> noire et maison 5 -> blanche #t_couleur=(t_couleur[0],)+('marron',)+(t_couleur[1],)+('noire','blanche') print("Progression : %d / 48" % progression) progression+=1 for t_instrument in tous_les_cas_instrument: # boucle 24 fois # on ajoute à la main le 5ème instrument de musique ('xylophone') dans la maison 3 : t_instrument=t_instrument[:2]+('xylophone',)+t_instrument[2:] for t_animal in tous_les_cas_animal: # boucle 120 fois for t_profession in tous_les_cas_profession: # boucle 120 fois for i in range(1,5+1): liste_maisons[i]['nationalité']=t_nationalite[i-1] liste_maisons[i]['profession']=t_profession[i-1] liste_maisons[i]['couleur']=t_couleur[i-1] liste_maisons[i]['animal']=t_animal[i-1] liste_maisons[i]['instrument']=t_instrument[i-1] # on teste cette solution : if solution(liste_maisons): solutions_trouvees=solutions_trouvees+1 print('Solution n°%d trouvée :' % solutions_trouvees) # affiche les solutions trouvées par le programme : print(liste_maisons) # on compte le nombre de solution testées : solutions_testees=solutions_testees+1 print('\nLe programme a testé par force brute %d solutions différentes et en a trouvé %d correctes.' % (solutions_testees,solutions_trouvees)) """ Résultat obtenu en testant le CAS 1 : Résultat obtenu en testant le CAS 2 : """