In versiunea initiala, puzzle-ul inventat de Sam Loyd in
1870, un cunoscut matematician si puzzleist cuprindea
o tabla de 4*4, cu piese numerotate de la 1 la 15 si un
spatiu. Nu exista doua piese cu acelasi numar.
Scopul jocului este asezarea pieselor de pe tabla in configuratia
finala.
O configuratie a tablei este considerata finala, daca
si numai daca, citind elementele ei de sus in jos si de
la stanga la dreapta obtinem sirul 1, 2, …, 15,_ .
Pentru a obtine aceasta configuratie finala, pe tabla
de joc, patratelul gol poate schimba locul cu oricare
dintre patratelele continand numere ce ii sunt vecine
(stinga, dreapta, sus si jos). De observat ca nu toate
permutarile initiale au solutie (exista un sir de mutari
posibile care sa conduca la configuratia finala).
De altfel, jumatate din permutarile posibile ale cifrelor
de pe tabla de joc sunt de neatins din configuratia finala.
Ca un fapt interesant, prima versiune comerciala publicata
de Sam Loyd cuprindea o configuratie initiala fara solutie,
si oferea un premiu de 1000 $ celui care oferea o solutie
corecta!!
Problema consta in gasirea unui numar optim de mutari
care sa conduca la configuratia finala (sau stabilirea
ca nu exista solutie pentru respectiva configuratie initiala).
Daca pentru o tabla 4*4 cu o configuratie initiala random
se poate gasi drumul spre solutie intr-un timp rezonabil,
problema se complica extrem de mult la o tabla de dimensiunea
5*5(cautarea solutiei putand dura de la ore la zile sau
chiar mai mult). O observatie interesanta este ca la o
tabla de tip romb solutia poate fi gasita mai repede datorita
existentei blocului "triunghi", care nu este
gasit in puzzleul 4*4(15 puzzle). Un rezultat remarcabil
a fost algoritmul de rezolvare a unei table 5*5 generata
random publicat de Korf.
Testeaza-ti si tu abilitatea in rezolvarea unui puzzle la www.megapuzzle.dazoot.ro
Adauga comentariu