# ========================================================================================= # Problème de logique : Qui joue du tambour ? # 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 surfaces 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. le propriétaire de la maison du milieu joue de la clarinette 2. la profession de Casimir est coiffeur 3. Raymond a des grenouilles 4. la maison de 260 m² est voisine de celle de Gilbert 5. la maison où il y a un aigle est à côté de celle du bûcheron 6. le cinéaste joue de l'harmonica 7. Pierre habite la maison de 370 m² 8. dans la maison de 160 m² il y a le programmeur 9. c'est du violon que le propriétaire de la maison de 250 m² joue 10. Gilbert habite la première maison à gauche 11. la maison de 330 m² est immédiatement à gauche de la maison de 250 m² 12. le programmeur habite une maison voisine de celle où il y a un chamois 13. le banquier élève un gorille 14. Mathieu joue de la mandoline La problématique à résoudre est : - Qui possède un perroquet ? - Qui joue du tambour ? ###################################################################################################### ATTENTION : tout ce qui est dans le programme ci-dessous correspond au problème « Qui possède un sanglier ? » Le travail à faire est de modifier tout le programme (code source Python + les commentaires) pour l'adapter à ce nouveau problème « Qui joue du tambour ? » ###################################################################################################### """ 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 : 12. l'Égyptien habite la première maison à gauche : maison 1 -> Égyptien 8. l'Égyptien habite à côté de la maison noire : maison 2 -> noire 6. dans la maison du milieu on boit une citronnade : maison 3 -> citronnade La condition qui n'a que 2 solutions (à tester séparément) est : 4. la maison verte est immédiatement à gauche de la maison rouge -> on sait que la maison 2 est noire donc : -> soit maison 3 -> verte et maison 4 -> rouge -> soit maison 4 -> verte et maison 5 -> rouge -> 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) : 1. le restaurateur habite la maison blanche 2. le Suisse boit du sirop d'orgeat 3. un chevreuil est dans la maison du serveur 5. le mécanicien boit de l'eau 7. le Français est voiturier 9. le propriétaire de la maison orange est le Finlandais 10. dans la maison rouge on boit du jus de raisin 13. l'Anglais a un âne 2 relations doubles (relations de voisinage) : 11. le restaurateur habite une maison voisine de celle où il y a une autruche 14. le sculpteur habite une maison voisine de celle où il y a une souris """ # ########################################################### # 8 conditions avec une seule boucle (donc rapide à tester) : # ########################################################### # ========================================================================================= # CONDITION 1 : # 1. le restaurateur habite la maison blanche for i in range(1,6): if tableau[i]['profession']=='restaurateur' and tableau[i]['couleur']!='blanche': return False # ========================================================================================= # CONDITION 2 : # 2. le Suisse boit du sirop d'orgeat for i in range(1,6): if tableau[i]['nationalité']=='Suisse' and tableau[i]['boisson']!='orgeat': return False # ========================================================================================= # CONDITION 3 : # 3. un chevreuil est dans la maison du serveur for i in range(1,6): if tableau[i]['profession']=='serveur' and tableau[i]['animal']!='chevreuil': return False # ========================================================================================= # CONDITION 5 : # 5. le mécanicien boit de l'eau for i in range(1,6): if tableau[i]['profession']=='mécanicien' and tableau[i]['boisson']!='eau': return False # ========================================================================================= # CONDITION 7 : # 7. le Français est voiturier for i in range(1,6): if tableau[i]['nationalité']=='Français' and tableau[i]['profession']!='voiturier': return False # ========================================================================================= # CONDITION 9 : # 9. le propriétaire de la maison orange est le Finlandais for i in range(1,6): if tableau[i]['nationalité']=='Finlandais' and tableau[i]['couleur']!='orange': return False # ========================================================================================= # CONDITION 10 : # 10. dans la maison rouge on boit du jus de raisin for i in range(1,6): if tableau[i]['couleur']=='rouge' and tableau[i]['boisson']!='raisin': return False # ========================================================================================= # CONDITION 13 : # 13. l'Anglais a un âne for i in range(1,6): if tableau[i]['nationalité']=='Anglais' and tableau[i]['animal']!='âne': return False # ########################################################### # 2 conditions avec 2 boucles (donc plus lente à tester) : # ########################################################### # ========================================================================================= # CONDITION 11 : # 11. le restaurateur habite une maison voisine de celle où il y a une autruche # cherchons la position de la maison du restaurateur : for i in range(1,6): if tableau[i]['profession']=='restaurateur': position_restaurateur=i # cherchons la positione de la maison de l'autruche : for i in range(1,6): if tableau[i]['animal']=='autruche': position_autruche=i if abs(position_restaurateur-position_autruche)!=1 : return False # ========================================================================================= # CONDITION 14 : # 14. le sculpteur habite une maison voisine de celle où il y a une souris # cherchons la position de la maison du sculpteur : for i in range(1,6): if tableau[i]['profession']=='sculpteur': position_sculpteur=i # cherchons la positione de la maison de la souris : for i in range(1,6): if tableau[i]['animal']=='souris': position_souris=i if abs(position_sculpteur-position_souris)!=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 boisson # 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 : 12. l'Égyptien habite la première maison à gauche : maison 1 -> Égyptien 8. l'Égyptien habite à côté de la maison noire : maison 2 -> noire 6. dans la maison du milieu on boit une citronnade : maison 3 -> citronnade 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 : 4. la maison verte est immédiatement à gauche de la maison rouge -> soit maison 3 -> verte et maison 4 -> rouge -> soit maison 4 -> verte et maison 5 -> rouge 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 boissons à 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,'boisson':None},\ {'nationalité':None,'profession':None,'couleur':None,'animal':None,'boisson':None},\ {'nationalité':None,'profession':None,'couleur':None,'animal':None,'boisson':None},\ {'nationalité':None,'profession':None,'couleur':None,'animal':None,'boisson':None},\ {'nationalité':None,'profession':None,'couleur':None,'animal':None,'boisson':None}] # liste des 4 nationalités (en plus de 'Égyptien' dans la maison 1) sous forme de tuple : liste_nationalite=('Suisse','Français','Finlandais','Anglais') # liste des 5 professions sous forme de tuple : liste_profession=('restaurateur','serveur','mécanicien','sculpteur','voiturier') # liste des 2 couleurs (en plus de 'noire' dans la maison 2 et de 'verte' et 'rouge' qui seront insérées dans le tableau) sous forme de tuple : liste_couleur=('blanche','orange') # liste des 5 animaux sous forme de tuple : liste_animal=('chevreuil','autruche','âne','souris','sanglier') # liste des 4 boissons (en plus de 'citronnade' dans la maison 3) sous forme de tuple : liste_boisson=('orgeat','eau','raisin','grenadine') 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_boisson=tuple(permutations(liste_boisson)) 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é ('Égyptien') dans la maison 1 : t_nationalite=('Égyptien',)+t_nationalite for t_couleur in tous_les_cas_couleur: # boucle 2 fois # on ajoute à la main la couleur 'noire' dans la maison 2, et les couluers 'verte' et 'rouge' : il y a 2 cas à tester # CAS 1 : maison 3 -> verte et maison 4 -> rouge t_couleur=(t_couleur[0],)+('noire',)+('verte','rouge')+(t_couleur[1],) # CAS 2 : maison 4 -> verte et maison 5 -> rouge #t_couleur=(t_couleur[0],)+('noire',)+(t_couleur[1],)+('verte','rouge') print("Progression : %d / 48" % progression) progression+=1 for t_boisson in tous_les_cas_boisson: # boucle 24 fois # on ajoute à la main la 5ème boisson ('citronnade') dans la maison 3 : t_boisson=t_boisson[:2]+('citronnade',)+t_boisson[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]['boisson']=t_boisson[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 : """