Nel post precedente abbiamo visto come creare il gioco del 15, oggi ci spingeremo ben oltre.
Il gioco del 15 è costituito da 16 pulsanti, dove il sedicesimo rappresenta lo spazio vuoto dove spostare le altre tessere, di base si può scrivere la configurazione della vittoria così:
| 1 | 2 | 3 | 4 |
| 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 |
che possiamo scriverla anche così:
1,2,3,4,
5,6,7,8,
9,10,11,12,
13,14,15,16
che possiamo scriverla anche così:
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
La sequenza di numeri che si presenta quando il gioco comincia è mescolata, il problema che mettendo le tessere a caso, non tutte le combinazioni possono essere risolte. Senza entrare troppo nel dettaglio,sappiate che per essere risolvibile un gioco del quindici, il numero di inversioni deve essere pari o dispari a seconda di alcune condizioni.
Per inversione si intende che nella sequenza scritta tutta in un unica riga, in numero piccolo viene dopo un numero grande; la casella vuota, il 16 nel nostro caso, non conta.
Ad esempio questa combinazione:
| 12 | 1 | 10 | 2 |
| 7 | 11 | 4 | 14 |
| 5 | | 9 | 15 |
| 8 | 13 | 6 | 3 |
si scrive così:
12,1,10,2,7,11,4,14,5,16,9,15,8,13,6,3
e in questa combinazione ci sono 49 inversioni, perchè:
- il 12 ha 11 inversioni dopo di sè
- il 10 ha 8 inversioni dopo di sè
- il 7 ha 4 inversioni dopo di sè
- il 11 ha 6 inversioni dopo di sè
- il 4 ha 1 inversioni dopo di sè
- il 14 ha 6 inversioni dopo di sè
- il 5 ha 1 inversioni dopo di sè
- il 9 ha 3 inversioni dopo di sè
- il 15 ha 4 inversioni dopo di sè
- il 8 ha 2 inversioni dopo di sè
- il 13 ha 2 inversioni dopo di sè
- il 6 ha 1 inversione dopo di sè
Se il numero 16, lo spazio vuoto, si trova su una riga pari, il numero di inversioni deve essere pari; se il 16 si trova su una riga dispari, il numero di inversioni deve essere dispari.
Nell'esempio appena mostrato, il 16 si trova sulla terza riga, dispari e il numero di inversioni è dispari, quindi è risolvibile.
Nel nostro programma, quando mescoliamo alla rinfusa i numeri, dobbiamo controllare se è risolvibile. In caso contrario la via più semplice è estrarre una nuova combinazione, poichè la metà delle combinazioni ottenibile è solvibile e il computer è più veloce a generare tantissime combinazioni fino ad ottenere una solvibile, piuttosto che altri metodi.
Il codice del programma va cambiato così:
on openCard
mescola
end openCard
on controllaVittoria
put the soluzione of me into ordine
repeat with i=1 to 16
put (the loc of button i ) & cr after temp
end repeat
if ordine = temp then
answer "Hai vinto!"
end if
end controllaVittoria
on impostaVittoria
repeat with i=1 to 16
put (the loc of button i ) & cr after temp
end repeat
set the soluzione of me to temp
end impostaVittoria
on mescola
put "1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16" into temp
put the soluzione of me into posizioni
repeat with i=1 to 16
put the number of items of temp into nn
put random(nn) into elemento
put item elemento of temp & CR after ordineBottoni
delete item elemento of temp #così leva anche la virgola
end repeat
put itemoffset("16",ordineBottoni) into n16
put controllasolv(ordineBottoni) into nInv
switch n16
case ((1 <= n16 ) and (n16 <= 4))
case ((9 <= n16 ) and (n16 <= 12))
#la casello vuota e' su una riga dispari
if (nInv mod 2) is 0 then mescola
break
case ((5 <= n16 ) and (n16 <= 8))
case ((13 <= n16 ) and (n16 <= 16))
#la casello vuota e' su una riga pari
if (nInv mod 2) is not 0 then mescola
break
end switch
repeat for each line tLine in ordineBottoni
set the loc of button tLine to the first line of posizioni
delete the first line of posizioni
end repeat
exit to top
end mescola
function controllasolv seq
put 0 into nInv
repeat with i=1 to 16
put item i of seq into temp
put item (i+1) to 16 of seq into tSeq
add inversioni(temp,tSeq) to nInv
end repeat
return nInv
end controllasolv
function inversioni t,seq
put 0 into nInv
repeat for each item tItem in seq
if (t > tItem) and (t is not 16) then
add 1 to nInv
end if
end repeat
return nInv
end inversioni
Detto ciò, il numero massimo per risolvere il gioco del 15 è di 80 mosse, ma calcolare la soluzione migliore per ogni configurazione richiede una potenza di calcolo spaventosa. Nel 2005 ci volevano settimane utilizzando super computers.
Potete utilizzare varie tecniche per trovare la soluzione, ma la migliore rimane quella di utilizzare un database.
Dalla soluzione, dovete cercare di arrivare alla sequenza di partenza, ogni mossa deve essere registrata nel database almeno nel seguente modo:
| n.mossa | sequenza | sequenza precedente |
In questo modo, se trovate una sequenza già eseguita, non dovete più proseguire e solo raffrontare il numero di mosse per arrivarci, per stabilire quale è la migliore. Se la nuova sequenza è già presente nel database e ci arrivate con un numero di mosse maggiore, allora non proseguite; in caso contrario cancellate dal database quella vecchia e lasciate quella nuova.
Inoltre segnare la sequenza precedente vi permette di andare a ritroso nella soluzione. Il database vi permette di trovare subito se una sequenza che è già stata elaborate precedentemente e non perde tempo nel calcolare la soluzione.
Finchè la tabella del database non raggiunge le 10'461'394'944'000 righe, voi non avrete la certezza di trovare la soluzione col minor numero di mosse; ma di sicuro troverete una nel minor tempo di elaborazione possibile.
Ogni volta che cercherete la soluzione ad una sequenza, il database diventerà sempre più grande e la ricerca sarà sempre più veloce.
Qui trovate alcuni link interessanti:
