# ========================================================================================= # Problème de logique : Qui possède un sanglier ? # 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 ont chacun un animal favori et une boisson préférée. Les données du problème sont : 1. le restaurateur habite la maison blanche 2. le Suisse boit du sirop d'orgeat 3. un chevreuil est dans la maison du serveur 4. la maison verte est immédiatement à gauche de la maison rouge 5. le mécanicien boit de l'eau 6. dans la maison du milieu on boit une citronnade 7. le Français est voiturier 8. l'Égyptien habite à côté de la maison noire 9. le propriétaire de la maison orange est le Finlandais 10. dans la maison rouge on boit du jus de raisin 11. le restaurateur habite une maison voisine de celle où il y a une autruche 12. l'Égyptien habite la première maison à gauche 13. l'Anglais a un âne 14. le sculpteur habite une maison voisine de celle où il y a une souris La problématique à résoudre est : Qui boit du sirop de grenadine et qui possède un sanglier ? """ 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 4 minutes environ) en testant le CAS 1 (maison 3 -> verte et maison 4 -> rouge) : 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 -> verte et maison 5 -> rouge) : 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 -> verte et maison 5 -> rouge) : Progression : 7 / 48 Solution n°1 trouvée : [None, {'couleur': 'blanche', 'nationalité': 'Égyptien', 'boisson': 'grenadine', 'profession': 'restaurateur', 'animal': 'souris'}, {'couleur': 'noire', 'nationalité': 'Suisse', 'boisson': 'orgeat', 'profession': 'sculpteur', 'animal': 'autruche'}, {'couleur': 'orange', 'nationalité': 'Finlandais', 'boisson': 'citronnade', 'profession': 'serveur', 'animal': 'chevreuil'}, {'couleur': 'verte', 'nationalité': 'Anglais', 'boisson': 'eau', 'profession': 'mécanicien', 'animal': 'âne'}, {'couleur': 'rouge', 'nationalité': 'Français', 'boisson': 'raisin', 'profession': 'voiturier', 'animal': 'sanglier'}] Il faut environ 4 minutes pour faire les 48 tests """