Newsgroup: it.hobby.enigmi
Titolo: Inversione di gettoni

8 gettono numerati da 1 a 8 sono messi in linea in posizione naturale:
1 2 3 4 5 6 7 8
Lo scopo:     Ottenere l'ordine inverso, ovvero 8 7 6 5 4 3 2 1.
La mossa:     2 gettoni qualunque vengono sollevati dal tavolo e
scambiati di posto.
Il vincolo:   In qualsiasi momento non ci devono essere 2 gettoni
adiacenti con la loro differenza >3.
In quante mosse lo fai ?
:) dario

Dario Uri propone

Giusto per rompere il ghiaccio.
Ci riesco in 16 mosse, e credo di esserci riuscito anche in 15, ma non
riesco a ricostruire la sequenza.
.
.
.
.
.
.
.
.
.
.
.
.
.
-> 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
--------------------------------------------------
1  1  1  1  1  1  1  1  1) 2  2  2  2) 6) 8  8  8
2  2  2  2  2) 4) 3  3  3  3) 4) 5  5  5  5) 7  7
3  3  3  3  3  3) 4  4) 5  5  5) 4  8  8) 6  6  6
4  4) 6  6  6  6  6) 7  7  7  7  7  7  7  7) 5  5
5  5  5) 7) 8  8  8  8  8  8  8  8  4  4  4  4  4
6) 8  8  8) 7  7  7) 6  6  6  6  6  6) 2  2  2) 3
7  7  7) 5  5  5  5  5) 4  4) 3  3  3  3  3  3) 2
8) 6) 4  4  4) 2  2  2  2) 1  1  1  1  1  1  1  1
--------------------------------------------------
Silv:o)

 
Ciao Silvio, 
Sei andato molto vicino al massimo! (minimo). 
La sol. in 14 e' veramente difficile da trovare.
ciao :) dario

Dario Uri <Da...@Uriland.it> wrote in message
3A8FAAA5...@Uriland.it...

15!Come aveva scritto anche Silvio Sergio
S
P
O
L
E
I
R
12543678
14523678
54123678
74123658
74123568
74125368
74521368
78521364
78521346
87521346
87531246
87631245
87635421
87653421
87654321
Walker

 La sol. in 14 e' veramente difficile da trovare.
lo sai che se dici così non posso tirarmi indietro...
.
.
.
.
.
.
.
.
.
.
.
.
.
00) 12345678
01) 21345678
02) 23145678
03) 24135678
04) 24136578
05) 64132578
06) 64312578
07) 46312578
08) 86312574
09) 86312547
10) 86352147
11) 86752143
12) 87652143
13) 87654123
14) 87654321
Silv:o)

 ha scritto nel messaggio
news:96tld8$mltf7$1...@ID-49224.news.dfncis.de...

Questo gioco mi è piaciuto, moltissimo. Io ovviamente non ero arrivato a
suluzioni accettabili e quindi pubblicabili.
Posso chiedere, così, tanto per imparare qualcosa, se per arrivare a quelle
brillanti soluzioni avete fatto un ragionamento logico, o se (non posso
credere che sia così) avete fatto prove su prove, fino a trovare la
soluzione ottimale?
In giochi simili (vedi anche sciusciammok), dopo aver dato la soluzione
ottimale, potreste spendere qualche parola per indicare a noi principianti
il metodo che avete seguito?
Siate didattici, così magari riusciamo ad imparare qualcosa anche noi, e
chissà tra qualche mese.........
Ciao a tutti.

 trovare la soluzione ottimale?
Posso solo narrarti la genesi della mia soluzione. Per esperienza diretta
posso dire che ogni problema fa storia a se, quindi non so se la cosa ti
potrà tornare utile, anche perché forse rimarrai deluso dallo cscoprire
che ho usato un programma.
Il mio primo tentativo è stato fatto puramente a mano, cercando di
spostare l'otto e l'uno uno o due passi alla volta, un po' dal capo e un
po' dalla coda. All'inizio vagheggiavo una soluzione simmetrica, per cui
avevo anche provato a fare le mosse a coppie, sui complementari, ma presto
ho abbandonato la pista. Arrivato alla soluzione in sedici (forse anche ad
una in quindici persa tra i miei scarabocchi) ho capito che difficilmente
sarei arrivato a quella in quattordici annunciata da Dario, ed ho
cominciato a pensare ad una soluzione algoritmica.
Ultimamente abbiamo discusso diverse volte dell'opportunità di usare la
forza bruta per risolvere problemi come questo, ed è risultata opinione
abbastanza diffusa che il nocciolo del problema sta nel rapporto tra
creatività e tecnica pura. Quando la seconda prevale allora il problema
perde molto appeal, anche se spesso i risultati sono decisamente
interessanti. Per rimanere al nostro caso: quanto è giustificato il
ricorso alla programmazione? Per conto mio, trovare la soluzione in 14 a
mano mi avrebbe dato sì qualche soddisfazione, ma mi sarebbe rimasto il
dubbio sulla casualità della scoperta, a meno di non usare tecniche in
qualche modo esaustive. Ma a questo punto non avrei fatto altro che
utilizzare un algoritmo, e allora tanto vale affidarsi alla macchina che
lavora meglio ed è infinitamente più veloce.
Io mi diverto molto a scrivere programi per risolvere i giochi. E se
"girano" al primo colpo la soddisfazione è doppia.
Stavolta ho dovuto fare diversi errori per arrivare alla soluzione.
Ho cominciato con una struttura che utilizzo nella stragrande maggioranza
dei problemi di questo tipo: esame esaustivo dell'albero delle soluzioni
tramite una "ricerca in profondità" implementata con una tecnica di
backtracking. Anche se suona molto tecnico, tutto l'ambaradan è abbastanza
semplice. In sostanza si parte da una configurazione e si comincia a
permutare due elementi portandosi in una nuova configurazione, a partire
dalla quale si permuta e così via, fino ad incontrare la soluzione o un
vicolo cieco. Allora si torna indietro e si permutano altri due elementi e
si esplora un altro ramo.
Primo problema. L'albero non è un albero ma un grafo. Ovvero: una
configurazione può essere raggiunta da più sequenze, per cui facilmente si
entra in loop infiniti. Per fare un esempio banale, parto da 12345678,
permuto i primi due e arrivo a 21345678. Se adesso facessi la stessa cosa
tornerei alla configurazione iniziale. Per cui si deve tener traccia delle
configuazioni già raggiunte, e anche del numero di passi necessari a
raggiungerle, in modo da abbandonare rami che erano già stati visitati, a
meno che la nuova visita non sia maggiormente promettente (minor numero di
passi necessari a raggiungere la stessa configurazione). Ci sono diverse
difficoltà da superare, ma tutto sommato è uno schema conosciuto (ricerca
in profondità). Metto in moto e mi accorgo che le prime soluzioni vengono
trovate in 500 (!) passi, poi moltissime altre in 450 e giù di lì. Spengo
tutto. Ci vorranno secoli per tornare nei rami bassi, se l'albero ha così
tanti livelli. Mi ci vorrebbe una bella cesoia per *potare* i rami secchi.
Allora imbroglio un po' (molto). Dato che so (Dario) che la soluzione
ottimale è in 14 mosse, al quattordicesimo livello metto una bella mannaia
(*If n=14 Then Exit Sub*) e guardo cosa succede. Con un po' di lentezza,
comincio a vedere che il programma staziona molto sugli ultimi livelli,
poi, man mano che le configurazioni vengono marcate come *raggiungibili*
comincia a tornare sui propri passi scendendo al livelli inferiori. Un
quarto d'ora dopo arranca provando un sesto livello dopo l'altro. Neanche
sto a pensarci e stoppo tutto. Se devo metterci una settimana ci rinuncio.
Allora mi viene l'idea: non è che sarà meglio una visita *a ventaglio*?
E' l'altro importante schema di visita di un grafo: si parte da una
configurazione, si analizzano *tutte* le possibili mosse, poi per ogni
possibile configurazione raggiungibile si fa la stessa cosa.
In pratica ci sono 26 possibili configurazioni con un singolo scambio; le
inserisco in un a lista, poi scandisco la lista e trovo le combinazioni
distanti due mosse dall'originale, avendo cura di non mettere due volte la
stessa e di evitare pure configurazioni raggiunte in meno passi. Come
sospettavo la crescita del numero delle configurazioni è contenuta, anzi
dopo i primi passi si inverte la tendenza.
1(26),2(55),3(136),4(129),5(87),6(52),7(49),8(56),9(54),10(70),11(100),12(
136),13(97),14(27),15(0)
La "87654321" è una dell 27 configurazioni raggiungibili in 14 mosse, e
può essere raggiunta da 13 (su 97) diverse configurazioni in 13 mosse.
Spero di esserti stato utile. L'algoritmo l'ho scritto in Visual Basic, se
vuoi altre specifiche chiedi pure.
Silv:o)

Ti ringrazio moltissimo.
Credo di aver capito quasi tutto.
Così mi piace ancor di più !!!!

 
Ottimo e complimenti davvero a Dario per il bel problema ed
a te per la soluzione.
Io ho provato una cosa simile ma con scarsi risultati.
Sarei curioso di vedere in quante righe e' fatto il tuo prg ?
Io dico al massimo 40. Che mi dici ? Posso averlo ?
CiaO,
Massimo

 Io dico al massimo 40. Che mi dici ? Posso averlo ?
Eccolo qui. Sono proprio 40 righe, più due di dichiarazione dei vettori :)
Se non hai VB puoi usare Excel, io l'ho scritto proprio con quello.
----------------
Sub scambi()
 Dim lista(15, 200) As String  'lista degli elementi, divisa per distanze
 Dim l(15) As Integer  'numero di elementi presenti per ogni distanza
  lista(0, 1) = "12345678"
  l(0) = 1  'numero di soluzioni di distanza zero
  d = 0     'distanza dalla stringa iniziale
  Do
    For k = 1 To l(d)  'scandisce tutte le disposizioni distanti d
      s = lista(d, k)  'estrae una disposizione
      For i = 1 To 7   'prova a scambiare tutte le possibili coppie
        For j = i + 1 To 8
          b = Left(s, i - 1) & Mid(s, j, 1)
          b = b & Mid(s, i + 1, j - i - 1) & Mid(s, i, 1) & Mid(s, j + 1)
          If b = "87654321" Then sol = sol + 1
          valida = True
          For n = 1 To 7  'controlla le differenze tra due elementi
adiacenti
            If Abs(Val(Mid(b, n, 1)) - Val(Mid(b, n + 1, 1))) > 3 Then
              valida = False
              Exit For
            End If
          Next n
          If valida Then  'controlla che non sia già in lista
            doppione = False
            For d1 = 0 To d + 1  'per tutte le distanze
              For k1 = 1 To l(d1)  'per tutte le conf in lista
                If lista(d1, k1) = b Then
                  doppione = True
                  Exit For
                End If
              Next k1
              If doppione Then Exit For
            Next d1
            If Not doppione Then
              l(d + 1) = l(d + 1) + 1 'incrementa il numero di elementi
presenti in lista
              lista(d + 1, l(d + 1)) = b 'inserisci b nella lista
            End If
          End If
        Next j
      Next i
    Next k
    d = d + 1
  Loop Until l(d) = 0
  Debug.Print sol
End Sub
------------------
Per come è fatto trova solo il numero di soluzioni e non le soluzioni
stesse.
Infatti non tiene traccia del percorso fatto.
Se vuoi trovare le soluzioni devi utilizzare uno stratagemma:
Sostituisci la riga
If b = "87654321" Then sol = sol + 1
con
If b = "87654321" Then Debug.Print s
in questo modo hai una lista delle 13 diposizioni di distanza 13 che
*confinano* con la 87654321
La prima di queste in questo caso sarà 87654123.
Lo scrivi al posto di "87654321" nellla riga di codice e trovi le parole
che confinano con questa. Ne prendi una e la metti nel codice e così via.
Farà schifo, ma a me serviva trovar UNA soluzione, e non tutte, quindi non
mi sono dannato più di tanto per risolvere il problema ;)
Silv:o)

 anzi dopo i primi passi si inverte la tendenza.
perň poi ho dato dei valori non esatti. Ecco quelli giusti.
dist. configurazioni
00     1
01    13
02    55
03   110
04   129
05    87
06    52
07    49
08    56
09    54
10    70
11   100
12   136
13    97
14    27
La cosa interessante č che il totale č 1036, mentre le permutazioni legali
sono 1042 (brute-force).
Questo vuol dire che ci sono 6 disposizioni legali (ovvero con differenze
tra elementi adiacenti non maggiori di 3) ma non raggiungibili tramite
permutazioni di elementi.
Sapete trovarle?
Silv:o)
(Hint: sono proprio *isolate*)

 
Credo che 4 delle 6 sono queste due:
85247631
86325741
con le rispettive speculari.....
13674258
14752368
Adesso e' tardi ma domani provo ancora.
CiaO,
Massimo

 La sol. in 14 e' veramente difficile da trovare.
Sarebbe carino sapere se anche Dario ha usato un
approccio computazionale come Silvio oppure ha
usato qualche "stregoneria" delle sue....
;-))
CiaO,
Massimo

Bene Massimo, manca una coppia un po' meno isolata
Silv:o)