# ========================================================================================= # Problème de logique : Qui possède un pingouin ? # 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 nationalités et de professions différentes 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 de compagnie. Les données du problème sont : 1. le chanteur habite une maison voisine de celle où il y a un caméléon 2. le traiteur habite la maison grise 3. le Japonais joue de la contrebasse 4. la profession de l'Irlandais est coiffeur 5. le Chilien habite à côté de la maison marron 6. dans la maison blanche on joue du hautbois 7. la maison blanche est immédiatement à droite de la maison noire 8. il n'y a pas de voisin à gauche de la maison du Chilien 9. le traiteur habite une maison voisine de celle où il y a un hippopotame 10. le propriétaire de la maison rouge est le Grec 11. dans la maison du milieu on joue du xylophone 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 La problématique à résoudre est : Qui joue de la clarinette et qui possède un pingouin ? """ 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)) """ Voici la solution attendue pour de ce problème du pingouin : Maison 1 Maison 2 Maison 3 Maison 4 Maison 5 nationalité --> Chilien Japonais Grec Français Irlandais profession --> traiteur chanteur charpentier restaurateur coiffeur couleur --> grise marron rouge noire blanche animal --> caméléon hippopotame autruche coq pingouin instrument --> clarinette contrebasse xylophone guitare hautbois Résultat obtenu (en 4 minutes environ) en testant le CAS 1 (maison 3 -> noire et maison 4 -> blanche) : Le programme a testé par force brute 16588800 solutions différentes et en a trouvé 0 correctes. Résultat obtenu (en 4 minutes environ) en testant le CAS 2 (maison 4 -> noire et maison 5 -> blanche) : Le programme a testé par force brute 16588800 solutions différentes et en a trouvé 1 correctes. Et voici la solution unique trouvée par ce programme Python (au bout d'1 minute environ) en testant le CAS 2 (maison 4 -> noire et maison 5 -> blanche) : Progression : 7 / 48 Solution n°1 trouvée : [None, {'couleur': 'grise', 'nationalité': 'Chilien', 'profession': 'traiteur', 'animal': 'caméléon', 'instrument': 'clarinette'}, {'couleur': 'marron', 'nationalité': 'Japonais', 'profession': 'chanteur', 'animal': 'hippopotame', 'instrument': 'contrebasse'}, {'couleur': 'rouge', 'nationalité': 'Grec', 'profession': 'charpentier', 'animal': 'autruche', 'instrument': 'xylophone'}, {'couleur': 'noire', 'nationalité': 'Français', 'profession': 'restaurateur', 'animal': 'coq', 'instrument': 'guitare'}, {'couleur': 'blanche', 'nationalité': 'Irlandais', 'profession': 'coiffeur', 'animal': 'pingouin', 'instrument': 'hautbois'}] Il faut environ 4 minutes pour faire les 48 tests Conclusion : si on remplit 5 cases dans le tableau, 8 minutes suffit à Python pour ressortir la solution finale du problème (2 tests de 4 minutes chacun). """