Aquesta és l’endevinalla: En un carrer hi ha cinc cases de colors diferents i en cada una hi viu una persona de nacionalitat diferent. Els cinc amos beuen tipus de begudes diferents, fumen marques de tabac diferents i cada un té un animal de companyia diferent al dels altres (per cert, la imatge de dalt la podeu trobar a aquesta pàgina web). El que sabem és això:
1. El britànic viu a la casa vermella.
2. El suec té un gos d’animal de companyia.
3. El danès beu te.
4. El noruec viu a la primera casa.
5. L’alemany fuma Prince.
6. La casa verda és immediatament a l’esquerra de la blanca.
7. El propietari de la casa verda beu cafè.
8. El propietari que fuma Pall Mall cria ocells.
9. El propietari de la casa groga fuma Dunhill.
10. L’home que viu a la casa del centre beu llet.
11. L’home que fuma Blends viu al costat del que té un gat.
12. L’home que té un cavall viu al costat del que fuma Dunhill.
13. L’home que fuma Bluemaster beu cervesa.
14. L’home que fuma Blends viu al costat del que beu aigua.
15. El noruec viu al costat de la casa blava.
I la pregunta és: qui és que té un peix com animal de companyia?
L’endevinalla és un bon exercici de combinatòria i una bona mostra de l’ús de tècniques algorísmiques per resoldre problemes amb l’ajut dels ordinadors. Analitzem el que ens diuen. En primer lloc, és fàcil veure que dins d’aquestes 15 pistes trobem el color de totes les cases (blanc, groc, verd, vermell i blau), la nacionalitat de tots els seus habitants (britànic, suec, danès, noruec i alemany), les seves begudes (te, cafè, llet, cervesa i aigua), el seu tabac (Prince, Pall Mall, Dunhill, Bluemaster i Blends) i el seu animal de companyia (gos, ocells, gat, cavall i peix). El que hem de fer és posar en ordre totes aquestes informacions de manera que quedin relacionades segons les pistes que ens donen. A més, també hem de trobar en quin ordre tenim les cases, perquè algunes preguntes (com la 6) justament ens parlen de relacions de veïnatge.
Quantes possibles solucions tindríem si no ens donessin cap pista? Suposem que numerem les cases al llarg del carrer, de la 1 a la 5. Podem assignar nacionalitats dels habitants a cada una de les 5 cases de 120 maneres diferents, perquè el nombre de permutacions de 5 elements és 120. Ara bé, també tenim 120 maneres d’assignar color a les cases, 120 maneres d’assignar begudes als habitants de cada casa, 120 maneres d’assignar-los tabac i 120 d’assignar els animals de companyia. En total, el nombre de possibilitats és 120 multiplicat per sí mateix 5 vegades, o sigui 120 a la cinquena potència. En altres paraules: si volem anar provant fins encertar-la, hem de saber que el nombre total de casos possibles que haurem d’analitzar és de més de vint-i-vuit mil milions.
Per resoldre el problema de manera més eficient, és molt útil tenir una bona representació de la solució. En el nostre cas, pot ser una taula de doble entrada amb 5 files i 5 columnes. A cada una de les files tenim la informació de una de les cases (ordenada de manera que tenim la primera casa del carrer a la primera fila i la darrera a la fila 5), i, a cada una de les columnes, informació sobre el color de la casa, la nacionalitat de la persona que hi viu, la seva beguda, la seva marca de tabac i el seu animal de companyia. També es bo analitzar i classificar les pistes per veure quines d’elles són més informatives. N’hi de tres tipus. La 4 i la 10 són pistes estàtiques que ens permeten posar informació ja definitiva a la taula: la nacionalitat de la fila 1 és noruega, i la beguda de la fila 3 és llet. En un segon grup, tenim vuit pistes (les 1, 2, 3, 5, 7, 8, 9 i 13) que ens informen de relacions binàries entre dos elements de la mateixa fila de la taula (vegeu nota al final). Finalment, les 5 pistes restants (6, 11, 12, 14 i 15) són relacions de veïnatge entre cases de files contigües. L’interessant de tot plegat és que, amb les dues pistes estàtiques, les vuit binàries i dues de les de veïnatge podem reduir dràsticament l’espai de cerca i passar de les més de vint-i-vuit mil milions de possibilitats a 288, tot convertint un problema intractable en un altre de fàcil solució.
Ara ja podem continuar amb raonaments basats en les relacions de veïnatge. Podeu trobar la solució completa del problema a moltes pàgines web, si us canseu de fer proves. Fins i tot teniu vídeos, com aquest, que ens mostren la solució (l’amo del peixet és l’alemany) i una estratègia de prova i error per trobar-la. En tot cas, el bonic de veure és que, amb no massa feina, hem passar d’haver de tractar aquests vint-i-vuit mil milions de casos a uns quants centenars. I això és justament el que fem quan pensem algorismes per resoldre problemes amb ordinador: a l’oceà de possibles solucions, intentem descartar, amb el mínim esforç, camins que sabem que no ens portaran enlloc. És una manera de podar l’arbre de solucions possibles fins que el nombre d’alternatives sigui tractable. Llavors, podem continuar podant o podem simplement provar, per cada una de les opcions candidates que ens han quedat, si satisfan la resta de pistes o restriccions del problema (que en el nostre cas són les cinc de veïnatge).
———
Per cert, en Bru Rovira diu que els mateixos que ploraven al Parlament Europeu durant l’acte d’entrega del premi Sàkharov a la llibertat d’esperit a la Nadia Murad i la Lamia Haji Bachar, van decidir la setmana passada que la UE podrà reenviar a Grècia, a partir del mes de març, els demandants d’asil que hagin entrat per aquest país.
———
NOTA: les vuit pistes (1, 2, 3, 5, 7, 8, 9 i 13) que codifiquen relacions binàries les podem expressar de manera compacte si anomenem les cinc files de la taula com C, N, B, T i A (color, nacionalitat, beguda, tabac i animal, respectivament. Direm que la pista 1 és N-C perquè ens relaciona la nacionalitat amb el color de la casa. De la mateixa manera, la pista 2 és N-A, i les altres sis relacions binàries són N-B, N-T, C-B, T-A, C-T i T-B. Són relacions que connecten elements d’una mateixa fila de la taula. Tenim quatre relacions N-x, mentre que el nombre de relacions que afecten altres columnes de la taula és menor. I ja sabem que el noruec viu a la casa 1, que la beguda de qui viu a la casa 3 és llet i que el color de la casa 2 és blau (pista 15). Veiem a més (per la relació N-C) que el britànic només pot viure a la casa 3 o a la casa 5 (no pot viure a la casa 1 perquè hi viu el noruec, ni a la casa 2 perquè és blava, ni a la casa 4 perquè en aquest cas, no tindriem cap parella de cases contigües que poguèssin ser verda i blanca, com requereix la pista 6). Tenim per tant dues possibilitats. Si el britànic viu a la casa 3, ja sabem tots els colors de les cases: la casa 2 ha de ser blava, la 3 ha de ser vermella, la 4 verda i la 5 blanca, i per tant, la casa 1 ha ser ser la groga). I en el cas que el britànic visqui a la casa 5, la casa 2 ha de ser blava, la 5 ha de ser vermella, la 3 verda i la 4 blanca, mentre que la casa 1 ha ser ser també la groga. En cada un dels dos casos, podem provar totes les possibilitats de la columna N, que ara són 6 (és el factorial de 3 i no de 5 perquè ja sabem que el noruec viu a la primera casa i que el britànic viu a la 3 o a la 5 segons el cas). Per cada una d’aquestes 6 possibilitats, les dues primeres columnes de la taula, C i N, ens queden ja determinades, així com un animal, dues begudes i dos tabacs (per les relacions N-A, N-B, N-T, C-B i C-T). Un cop fet això, la columna més determinada passa a ser la de la beguda, perquè sabem que la de la casa tercera és llet i en sabem dues més per les relacions N-B i C-B. Per tant, a la columna de la beguda tenim 2 possibilitats (factorial de 2), i encara hem d’usar les relacions N-T, T-A, C-T i T-B. Passem ara a treballar amb la columna del tabac, que és la que surt a les relacions N-T, T-B i C-T. Un cop més tenim 2 possibilitats (factorial de 2) pel fet de tenir 3 relacions. Finalment, a la columna dels animals, les relacions N-A i T-A ens redueixen les possibilitats a 6 (factorial de 3). En resum: utilitzant la informació de les dues pistes estàtiques, de les vuit pistes binàries i de dues de les pistes de veïnatge (la 6 i la 15), veiem que només hem de provar 2*6*2*2*6 possibilitats (2 possibilitats de casa pel britànic, 6 per la resta de nacionalitats, 2 per la beguda, 2 pel tabac i 6 per l’animal). El total és 2*6*2*2*6 = 288. Estem parlant de menys de 300 possibilitats que haurem de provar ara en relació a les 3 pistes de veïnatge que encara no hem considerat.
