Newsgroup: it.hobby.enigmi
Titolo: La casetta

Tutti conoscono il gioco della casetta. Un grafo da percorrere senza
staccare la penna dal foglio e senza passare 2 volte sulla stessa linea.
Per riuscirci basta iniziare da uno dei due nodi dispari A o B e
terminare nell'altro.
       /\
      /  \
     /    \
    /      \
   /        \
  /__________\
  |\        /|
  | \      / |
  |  \    /  |
  |   \  /   |
  |    \/    |
  |    /\    |
  |   /  \   |
  |  /    \  |
  | /      \ |
  |/________\|
  A          B        
La domanda (un po' perfida) e': in quanti modi distinti puo' essere
fatto??
:) dario

...


fatto??
Azz, se è perfida !!!...
Tenendo presente che un percorso valido deve cominciare da A e finire in B, o viceversa, consideriamo solo i percorsi che iniziano
da A (essendo la partenza da B speculare e quindi topologicamente equivalente).
Io ho trovato 44 soluzioni distinte !!!
Utilizzando lo schema seguente:
       D
       /\
     /    \
E   -----   C
     |\    /|
     |  \/  |
     |  /\  |
     |/    \|
A  ------  B
le soluzioni sono:
ABCAECDEB
ABCAEDCEB
ABCDEACEB
ABCDECAEB
ABCEACDEB
ABCEDCAEB
ABEACDECB
ABEACEDCB
ABECAEDCB
ABECDEACB
ABEDCAECB
ABEDCEACB
ACBAECDEB
ACBAEDCEB
ACBECDEAB
ACBEDCEAB
ACDEABCEB
ACDEABECB
ACDEBAECB
ACDEBCEAB
ACDECBAEB
ACDECBEAB
ACEABCDEB
ACEABEDCB
ACEBAEDCB
ACEBCDEAB
ACEDCBAEB
ACEDCBEAB
AEBACDECB
AEBACEDCB
AEBCDECAB
AEBCEDCAB
AECABCDEB
AECABEDCB
AECBACDEB
AECBEDCAB
AECDEBACB
AECDEBCAB
AEDCABCEB
AEDCABECB
AEDCBACEB
AEDCBECAB
AEDCEBACB
AEDCEBCAB
Sperando di non aver detto l'ennesima castroneria...
--
Er Roscio.

 Io ho trovato 44 soluzioni distinte !!!
44 sono giuste se non tieni conto del nodo formato dall'incrocio delle
diagonali. Altrimenti sono tante di piu'. (ricordi, avevo detto
<perfida>). Ci sono metodi astuti per contare i percorsi possibili su un
grafo senza doverli provare tutti.
ciao dario

 Utilizzando lo schema seguente:

Ho paura siano molte di piu', almeno il doppio.
Ce ne sono 32 che iniziano con A-B!
Oggi pomeriggio cerchero' di dire quante in totale sono per me.
Ciao
Andrea
P.S. Sarebbe tanto piu' semplice fare un programmino che le conti!
Comunque devi considerare il nodo al centro nei vari percorsi.
--
Posted from [208.163.206.1]
via Mailgate.ORG Server - 
http://www.mailgate.org

 :) dario
 / \
D---C
|\ /|
| E |
|/ \|
A---B
Non metto la lettera sul tetto per cui CD e' percorribile in 2 modi,
quindi mi basta raddoppiare il numero di percorsi ottenuti nel modo seguente.
Ogni percorso (da A a B) valido ha le seguenti caratteristiche:
Vi appaiono esattamente 2 volte tutte le lettere da A ad E.
Per cui bisognerebbe riempire le otto caselle vuote A........B,
con 1A,1B,2C,2D,2E. (7! combinazioni)
Ovviamente da tutte le combinazioni vanno tolte quelle:
a) dove una lettera appare2 volte consecutive,
b) dove le combinazioni contengono una sequenza del tipo x y x dove x = a,b,e.
c) dove ci sia una sequenza che contenga AC o CA o BD o DB
d) dove non esiste almeno un CD o un DC
Fatto cio' abbiamo tutte le combinazioni buone. Calcolarle pero' e' arduo.
Forse andava affrontato mettendo delle lettere per gli archi.
Comunque il mio rislutato, ottenuto a mano e' di 110 vie diverse.
Potrebbero essere di piu' se mi sono sbagliato, ma non di meno.
Se fosse giusto (non si sa mai!) le posso anche impostare.
Spero mi venga in mente un approccio migliore.
Ciao!
Andrea


Comunque devi considerare il nodo al centro nei vari percorsi.
Appunto... me lo ha fatto notare anche Dario... semplicemente non l'ho neanche visto !!!
'speta che te lo dico... ma credo che siano ben più di 88...
--
Er Roscio.

grafo senza doverli provare tutti.
Ehehehehe... ho fatto proprio così...
Ho fatto tre grafi (uno solo non sarebbe entrato in una pagina):
uno per A-B (12 soluzioni), uno per A-C (16 sol.) e uno per A-E (16 sol.)
ho potuto notare che anche i rami "secchi" (quelli che non portano ad una soluzione) finiscono in B
--
Er Roscio.

fatto??
 _
|_
 _|
 _
|_|
|
 _
| |
|_|
 |
 |
|
|_
 _
|_
|_
 _
|_|
| \
||
||
\/
120
44 col primo tratto verticale, 44 diagonale e 32 orizzontale.
Due domande:
La presenza del 44, gia' trovato da Roscio, e' casuale?
Qual e' il modo "furbo" di contare le soluzioni?
Io l'ho risolto col seguente algoritmo ricorsivo (un adattamento di un noto
algoritmo di visita di un grafo)
Visita (grafo, nodo)
 PER OGNI arco non ancora utilizzato uscente da nodo
   segna l'arco come "utilizzato"
   SE archi finiti ALLORA
     stampa soluzione
     ESCI
   ALTRIMENTI
     Visita (grafo_aggiornato, nodo_arrivo)
La chiamata principale e'
Visita(grafo_completo, nodo "A")
Ciao, Silv:o)


Ciao Silvio, effettivamente come dicevo per il primo tratto AB esistono 32
soluzioni.
Per gli altri 2 tratti iniziali mi sono dimenticato qualche strada facendo in
fretta :-).
Da'ltra parte sono piu' imteressato a imparare un procedimento migliore piu'
che altro.
Ti diro' che programmoper lavoro tutto il giorno, per cui considero le
soluzioni via software non valide, per me intendo, nel senso che non le uso.
Sono in attesa anche io di sapere come scomporre il grafo in maniera da
calcolare semplicemente il numero di soluzioni.
Ciao
Andrea