Logica al calcolatore: il Puzzle di Einstein

Tenetevi pronti, che nell’epoca dei Social Network e di Ugo Qualunque stiamo per essere invasi dall’ennesimo quesito “solo per veri geni”. Sta già dilagando su WhatsApp e arriverà prestissimo su Facebook, quindi meglio prepararsi per tempo.

Va però ammesso che il nuovo tormentone  è interessante perché riporta in auge il tema della logica del primo ordine, nonché dei problemi basati su restrizione di uno spazio di ricerca attraverso proprietà specifiche dei dati imposti in forma di assiomi.

Va da sé che il ciarpame che gira nei Social è rarissimamente innovativo e, quasi sempre, è frutto di un riciclo di cose talmente vecchie da essere riconducibili tranquillamente all’era pre-internet. E così è anche in questo caso.

Ma andiamo con ordine: il “quiz per veri geni” che sta girando in questi giorni va sotto il nome di Puzzle di Einstein, perché si vuole che sia stato inventato dallo stesso genio tedesco. Ovviamente così non è, anche perché Einstein era un fisico e non un logico. Il puzzle è disponibile in innumerevoli versioni, come vuole la palta da Social Network, tutte equivalenti. Noterete infatti che quella dell’immagine di apertura in inglese è diversa dalla seguente, tratta da Wikipedia in Italiano:

In una strada ci sono 5 case dipinte in 5 colori diversi. In ogni casa vive una persona di differente nazionalità e ciascuno dei padroni di casa beve una bevanda diversa, fuma una marca di sigarette diversa, tiene un animaletto diverso. Le case sono disposte in ordine dalla prima alla quinta, e valgono i seguenti indizi:

1. L’inglese vive nella casa rossa.
2. Lo spagnolo è proprietario del cane.
3. Il caffè è bevuto nella casa verde.
4. Il tè è bevuto dall’ucraino.
5. La casa verde è immediatamente a destra della casa avorio.
6. Il fumatore Old Gold possiede lumache.
7. Le Kool sono fumate nella casa gialla.
8. Il latte si beve nella casa in mezzo.
9. Il norvegese vive nella prima casa.
10. L’uomo che fuma Chesterfield vive nella casa accanto all’uomo con la volpe.
11. Le Kool sono fumate nella casa vicino a quella dove si tiene il cavallo.
12. Chi fuma le Lucky Strike beve succo d’arancia.
13. Il giapponese fuma Parliament.
14. Il norvegese vive vicino alla casa blu.

Chi beve acqua e chi possiede la zebra?

Come non ricordare la meravigliosa collana di libri di Martin Gardner, “Enigmi e Giochi Matematici”? Ecco, questo problema è risolvibile tranquillamente mediante un processo puramente meccanico, che di geniale ha veramente poco. Va detto che il genio sta nell’ideare il processo, ma questa – si – è materia per pochi.

In “Enigmi e Giochi Matematici vol. 2”, il capitolo 11 “Logica Ricreativa”, racconta proprio come questo genere di giochi sia stato in gran voga ai tempi del brillante enigmeista inglese Henry Dudeney, ma anche ampiamente praticato da Lewis Carrol, che vi si dilettava non poco. Vi invito a rileggerlo.

Ecco il problema di Dudeney:

1. Smith, Jones e Robinson sono ingegnere, frenatore e fuochista di un treno. Sul treno ci sono però anche tre signori dallo stesso nome, identificati come Sig. Smith, Sig. Jones, Sig. Robinson. E non sono gli stessi dei primi tre.
2. Il Sig. Robinson vive a Los Angeles.
3. Il frenatore vive ad Omaha.
4. Il Sig. Jones ha dimenticato l’algebra imparata alle superiori.
5. Il passeggero che ha lo stesso nome del frenatore vive a Chicago.
6. Il frenatore ed uno dei passeggeri, un eminente fisico, frequentano la stessa chiesa.
7. Smith batte il fuochista a biliardo.

Chi è l’ingegnere?

Entrambe i problemi sono in realtà di logica matematica, e vanno affrontati attraverso un processo di mutua esclusione. Il problema di Dudeney si risolve scrivendo due tabelle di associazione nomi di persone e professioni, nomi di persone e città di residenza.

Il problema è formulato in modo tale che una persona possa vivere in una sola città ed esercitare una sola professione. Quindi, nelle tabelle dobbiamo scrivere V per “vero” in una sola casella di ciascuna riga mentre per il resto delle caselle della stessa riga e colonna scriveremo F per “falso”, ecco le tabelle da riempire tratte dal libro di M. Gardner:

Procedendo in modo iterativo, quindi ripassando su tutti i dati a turno, è possiblie man mano riempire le due tabelle in modo che vi sia un solo V per riga e colonna e, per tutte le altre, F. Quindi, se in una riga rimane un solo spazio libero in mezzo a tutte F, quello sarà il fatto necessariamente vero da marcare con V. Viceversa, marcando con V un fatto, tutti gli altri della stessa riga e colonna vanno marcati con F. Dopo pochi passaggi si ottiene la soluzione cercata. Un processo semplicissimo da implementare in un calcolatore elettronico.

Quindi, se volete dilettarvi con il presunto puzzle di Einstein, basta scrivere stavolta non due ma cinque tabelle, rispettivamente Casa / Colore, Casa / Nazionalità, Casa / Bibita, Casa / Animale, Casa / Sigarette.  Le Case vanno numerate da 1 a 5, in modo da avere l’informazione della posizione: case contigue avranno numeri contigui.

E, così, entrare nel novero dei “veri geni”. Ma, con buona pace dei Social Network, la cosa veramente interessante è che questo processo – a tutti gli effetti di deduzione – è implementabile  al calcolatore. Ed è la porta verso i sistemi sistemi esperti, ovvero applicazioni in grado di ragionare autonomamente.