SVM n°15 mars 1985
SVM n°15 mars 1985
  • Prix facial : 16 F

  • Parution : n°15 de mars 1985

  • Périodicité : mensuel

  • Editeur : Excelsior Publications

  • Format : (206 x 283) mm

  • Nombre de pages : 156

  • Taille du fichier PDF : 151 Mo

  • Dans ce numéro : rencotre avec des génies... Clive Sinclair, Bill Gates, Chuck Peddle, Steve Wozniak, Thomas Kurtz.

  • Prix de vente (PDF) : gratuit

Dans ce numéro...
< Pages précédentes
Pages : 76 - 77  |  Aller à la page   OK
Pages suivantes >
76 77
Barre Canne Croix Béquille COMME UN DOMINO EST UN ASSEMblage de deux carrés, un pentomino est une surface connexe constituée de cinq carrés. La figure 1 vous le montre d'emblée : il existe douze façons différentes, aux rotations et réflexions près, d'assembler cinq carrés d'un seul tenant, Le cassetête imaginé par Samuel Colombconsiste à ranger ces douze pentominos dans un rectangle : l'ampleur du problème ne vous aura certainement pas échappé si vous avez déjà tenté de le résoudre vous-même ! La surface totale étant de 5 x 12 soit 60 carrés élémentaires, les dimensions du rectangle peuvent être 6x 10, 5 x 12, 4 x 15 et 3 x 20 (le plus grand côté d'un pentomino étant toujours supérieur ou égal à 3, la solution 2 x 30 est exclue d'office). Si le rec'angle de dimensions 3 x 20 n'admet que deux solutions, tous les autres en admettent un très grand nombre (de un à plusieurs milliers). Ce casse-tête a déjà été complètement résolu à l'aide d'ordinateurs. Il fait appel à des techniques de programmation intéressantes et c'est pourquoi nous vous proposons de l'attaquer avec votre propre microordinateur. L'exploration de l'arbre des possibilités (figure 2), c'est-à-dire la recherche systématique des solutions, se fait en ajoutant les pièces une à une, toujours dans le même ordre, jusqu'à ce que vous soyez bloqué ou que vous ayez trouvé une solution. Si vous êtes bloqué, revenez à l'étape précédente et modifiez soit la position soit l'orientation de la dernière pièce posée. Sans succès, vous devrez reculer encore d'un cran et ainsi de suite. C'est le principe même de tous les casse-têtes : on pose quelques pièces et une fois dans le cul-de-sac, on retire quelques éléments pour essayer autre chose. La différence entre l'ordinateur et vous, c'est que vous tâtonnez, vous laissez faire votre intuition, alors que l'ordinateur garde la trace de toutes ses tentatives et continue méthodiquement, en analysant toutes les possibilités. Cet algorithme qui procède par exploration en avant et retour en arrière, est appelé "back-track" (retour sur ses pas). Il peut être appliqué à de nombreuses situations 1—] LES DOUZE PENTOMINOS Pont Chaise W Equerre Figure 1 1 où seule l'exploration systématique garantit la totalité des solutions. L'importance du néant ! Chaque fois qu'une nouvelle pièce est posée, la situation antérieure est enregistrée à la fin de la liste. Ainsi, lorsque le programme entreprend une marche arrière, il retrouve cette situation et sait ainsi exactement où il en est. Ce type de liste où l'on rajoute ou retire le dernier élément s'appelle une pile. Le programme "PAVÉ" utilise deux piles, qu'il fait ou défait simultanément. L'une, TAO, contient tous les états intermédiaires du pavage, et l'autre, PILE (), gère la position et l'orientation PAVÉ 10 DIM NO(12),PT(12,8,8).PILE(12,3),PV(2.20) 20 NE = 6:NC = 10 30 DIM TA(NE.NC,13),T(NE,NC) 100 FOR I = 1 TO 12 : READ NO(I) : NLXT 110 FOR I = 1 TO 12 : FOR J = 1 TO NO(I) : FOR V = 1 TO 8 : READ PT(I,J,K) : NLX1 NEXT : NEXT 130 P = 1 : FOR I = 1 TO 3:PILE(P.1) = 1 : NEXT 1000 IF TA(PIEE(P.1),PILE(P,2),P) < > 0 I HLN 2000 1010 FOR K = 1 TO 7 STEP 2 1020 I1 = PILE (P, 1) + PT (P,PILE (P, 3), K) 1030 JI = PILE(P,2) + PT(P.PIEE(P,3),K + 1) 1040 IF II > NE OR II < 1 THEN 1900 1050 IF JI) NC OR Ji < 1 THEN 1900 1060 IF TA(I1,J1,P) < > 0 THEN 1900 1070 NEXT K 1080 FOR I = 1 TO NE : FOR J = 1 TO NC:TA(I.J.P NEXT J : NEXT I 1090 TA(PILE(P,1),PILE(P,2),P + 1) = P 1100 FOR K = 1 TO 7 STEP 2 1110 TA(PILE(P,1) + PT(P,PILE(P.3),K), Bloc 1I + 1) = TA(I,J,P) : n L_I 1 Baïonnette de tous les pentominos utilisés à chaque niveau. Le "back track" simple vous garantit de trouver toutes les solutions, à condition d'être très patient ! En effet, le programme va bêtement continuer à explorer des branches de l'arbre dont on peut savoir très tôt qu'elles seront des impasses. Par exemple, si on pose la croix dans un coin (voir figure 3), il est évident que la case du coin ne pourra jamais être recouverte par un pentomino. Cela vaut pour tout groupe de deux, trois ou quatre cases vides isolées qui ne pourront pas être recouvertes puisqu'un pentomino a besoin d'au moins cinq cases vides pour pouvoir être posé. Ainsi. 76 SCIENCE & VIE MICRO N" 15 - MARS 1985 1
tout ensemble de cases vides d'un seul tenant doit contenir un nombre de cases multiple de 5 pour pouvoir être rempli exactement par des pentominos. Dès lors qu'apparaît dans l'exploration de l'arbre un nombre de cases non multiple de 5, il est inutile d'aller plus loin. La figure 3 illustre le type d'impasse dans laquelle vous pouvez vous trouver. L'astuce est donc de considérer l'état des cases vides formant ce que nous n'hésiterons pas à appeler des "trous". Le fait d'éliminer les branches qui comportent des "mauvais" trous n'est pas dérisoire, il fait gagner un bon facteur 10, c'est-à-dire que plus de 90% des branches sont ainsi éliminées. Reste à compter les cases de chaque trou... La notion de quelque chose "d'un seul bloc" est en effet assez difficile à préciser formellement, et encore plus à transcrire en Basic. En fait, le problème est analogue à celui du coloriage d'un contour fermé. Nous allons colorier notre trou et compter chaque case coloriée. Nous saurons ainsi combien ce dernier comporte de cases. Le principe du coloriage est représenté sur la figure 4. Le programme "PAVÉ" utilise cet algorithme pour compter les cases vides de chaque trou et éloigner ainsi les impasses. Cet algorithme est général et peut être appliqué à n'importe quel problème de coloriage. Le programme -PAVÉ" Suivant les principes décrits ci-dessus, le programme "PAVÉ" essaye de remplir un rectangle de dimensions NL, NC avec les douze pentominos dont la définition des formes est PILE(P,2) + PT(P,PILE(P,3).K+1),P+1) = P : NEXT K 1120 P = P + 1 : IF P = 13 THEN GOSUB 3000 : GOTO 2050 1125 PRINT P-1 : FOR I = 1 TO NL : FOR J = 1 TO NC : IF TA(I,J.P) = 0 THEN PRINT "." GOTO 1128 1126 PRINT CHR$ (ASC ("A") + TA(I.J,P) — 1) ; 1128 NEXT J : PRINT : NEXT I : PRINT 1130 FOR I = 1 TO 3:PILE(P,I) = 1 : NEXT : , GOTO 6000 1900 K = 7 : NEXT K 2000 IF PILE(P.3) < NO(P) THEN PILE(P.3) = PILE(P.3) + 1 : GOTO 1000 2010 PILE(P,3) = 1 2020 IF PILE(P.2) < NC THEN PILE(P.2) = PILE(P,2) + 1 : GOTO 1000 2030 IF PILE(P.1) < NL THEN PILE(P.1) = PILE(P.1) + 1 : PILE(P.2) = 1:GOTO 1000 2050 P = P — 1 : IF P = 0 THEN END 2060 GOTO 2000 3000 FOR I = 1 TO NL : FOR J = 1 TO NC : contenue dans les DATA. A partir d'une case,de référence (coordonnées 0,0), les quatre autres cases du pentomino sont définies en coordon- PRINT TA(I,J,12) NEXT : PRINT : NEXT : PRINT 3010 INPUT "ON CONTINUE ? " ; R$ : IF LEFT$ (R$‘1) = "N" THEN END Suite page 78 Figure 2 nées relatives. Pour chacun, toutes les orientations possibles sont prises en compte (1 pour la croix, 2 pour la barre, 8 pour la canne, etc). Le programme va essayer de placer les pentominos en tenant compte de leur ordre d'apparition dans les DATA. Si vous voulez chercher dans un autre ordre, il suffit de modifier l'ordre des blocs de DATA correspondants, à condition de modifier également la première ligne de DATA qui contient le nombre de lignes réservées à chaque pentomino. Le programme affiche étape par étape ses essais, vous invitant ainsi à suivre ses tâtonnements. Après les premières lignes d'initialisation, le corps du programme est constitué par les lignes 1000 à 2030 (empilement) et 2050 (retour en arrière). Le sous-programme en 5000-6000 est chargé du comptage des cases vides et de l'élimination des impasses. Le sous-programme en 3000 affiche les solutions. La variable P contient la profondeur d'exploration et est affichée à chaque nouvelle étape en même temps que l'état du pavage. La recherche est longue, plusieurs heures et même plusieurs jours, mais vous pourrez suivre sa progression. Le calcul pour le rectangle 6 x 10 est le plus lent, car c'est celui sur lequel les contraintes sont les plus faibles. Comptez 24 h pour obtenir la première solution. Sur le rectangle 4 x 15, les recherches peuvent durer plusieurs jours, mais sans l'amélioration de l'algorithme, ce serait dix fois plus long ! Un conseil : essayez d'abord avec le rectangle 3 x 20 : la première solution apparaît au bout de 12h, et la deuxième seulement 6 h plus tard... Frédéric NEUVILLE SCIENCE & VIE MICRO N°15 - MARS 1985 77



Autres parutions de ce magazine  voir tous les numéros


Liens vers cette page
Couverture seule :


Couverture avec texte parution au-dessus :


Couverture avec texte parution en dessous :


SVM numéro 15 mars 1985 Page 1SVM numéro 15 mars 1985 Page 2-3SVM numéro 15 mars 1985 Page 4-5SVM numéro 15 mars 1985 Page 6-7SVM numéro 15 mars 1985 Page 8-9SVM numéro 15 mars 1985 Page 10-11SVM numéro 15 mars 1985 Page 12-13SVM numéro 15 mars 1985 Page 14-15SVM numéro 15 mars 1985 Page 16-17SVM numéro 15 mars 1985 Page 18-19SVM numéro 15 mars 1985 Page 20-21SVM numéro 15 mars 1985 Page 22-23SVM numéro 15 mars 1985 Page 24-25SVM numéro 15 mars 1985 Page 26-27SVM numéro 15 mars 1985 Page 28-29SVM numéro 15 mars 1985 Page 30-31SVM numéro 15 mars 1985 Page 32-33SVM numéro 15 mars 1985 Page 34-35SVM numéro 15 mars 1985 Page 36-37SVM numéro 15 mars 1985 Page 38-39SVM numéro 15 mars 1985 Page 40-41SVM numéro 15 mars 1985 Page 42-43SVM numéro 15 mars 1985 Page 44-45SVM numéro 15 mars 1985 Page 46-47SVM numéro 15 mars 1985 Page 48-49SVM numéro 15 mars 1985 Page 50-51SVM numéro 15 mars 1985 Page 52-53SVM numéro 15 mars 1985 Page 54-55SVM numéro 15 mars 1985 Page 56-57SVM numéro 15 mars 1985 Page 58-59SVM numéro 15 mars 1985 Page 60-61SVM numéro 15 mars 1985 Page 62-63SVM numéro 15 mars 1985 Page 64-65SVM numéro 15 mars 1985 Page 66-67SVM numéro 15 mars 1985 Page 68-69SVM numéro 15 mars 1985 Page 70-71SVM numéro 15 mars 1985 Page 72-73SVM numéro 15 mars 1985 Page 74-75SVM numéro 15 mars 1985 Page 76-77SVM numéro 15 mars 1985 Page 78-79SVM numéro 15 mars 1985 Page 80-81SVM numéro 15 mars 1985 Page 82-83SVM numéro 15 mars 1985 Page 84-85SVM numéro 15 mars 1985 Page 86-87SVM numéro 15 mars 1985 Page 88-89SVM numéro 15 mars 1985 Page 90-91SVM numéro 15 mars 1985 Page 92-93SVM numéro 15 mars 1985 Page 94-95SVM numéro 15 mars 1985 Page 96-97SVM numéro 15 mars 1985 Page 98-99SVM numéro 15 mars 1985 Page 100-101SVM numéro 15 mars 1985 Page 102-103SVM numéro 15 mars 1985 Page 104-105SVM numéro 15 mars 1985 Page 106-107SVM numéro 15 mars 1985 Page 108-109SVM numéro 15 mars 1985 Page 110-111SVM numéro 15 mars 1985 Page 112-113SVM numéro 15 mars 1985 Page 114-115SVM numéro 15 mars 1985 Page 116-117SVM numéro 15 mars 1985 Page 118-119SVM numéro 15 mars 1985 Page 120-121SVM numéro 15 mars 1985 Page 122-123SVM numéro 15 mars 1985 Page 124-125SVM numéro 15 mars 1985 Page 126-127SVM numéro 15 mars 1985 Page 128-129SVM numéro 15 mars 1985 Page 130-131SVM numéro 15 mars 1985 Page 132-133SVM numéro 15 mars 1985 Page 134-135SVM numéro 15 mars 1985 Page 136-137SVM numéro 15 mars 1985 Page 138-139SVM numéro 15 mars 1985 Page 140-141SVM numéro 15 mars 1985 Page 142-143SVM numéro 15 mars 1985 Page 144-145SVM numéro 15 mars 1985 Page 146-147SVM numéro 15 mars 1985 Page 148-149SVM numéro 15 mars 1985 Page 150-151SVM numéro 15 mars 1985 Page 152-153SVM numéro 15 mars 1985 Page 154-155SVM numéro 15 mars 1985 Page 156