Igra 15 pazli
Igra 15 pazli (engl. Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square) je klizna slagalica koja se sastoji od rama u kojem se nalaze kvadratne pločice poređane po slučajnom redosledu pri čemu jedna pločica nedostaje. Ova slagalica postoji i u drugim veličinama, poput manje "igre 8 pazli". Ako je odnos pločica 3x3, onda se zove "igra 8 pazli" ili "igra 9 pazli", a ako ima odnos pločica 4x4, onda je to "igra 15 pazli" ili "igra 16 pazli".
Cilj slagalice je poređati pločice po rastućem poretku (kao što je prikazano na slici), kliznim pomeranjem jedne po jedne pločice na prazan prostor. Ova igra predstavlja klasičan problem modelovanja algoritma koji koristi heuristiku. Najčešće korišćena heuristika za ovaj problem uključuje brojanje pogrešno postavljenih pločica i pronalaženje rastojanja između svakog bloka i njegovog ciljnog položaja.
Džonson i Stori su 1879. godine iskoristili argument pariteta da pokažu da je polovinu početnih konfiguracija nemoguće rešiti, bez obzira koliko poteza je napravljeno. Došli su do ovog zaključka posmatrajući funkciiju konfiguracija pločica koja je nepromenljiva nakon bilo kog poteza, i zatim iskoristili ovo da podele prostor svih mogućih obeleženih stanja u dve ekvivalentne klase mogućih i nemogućih stanja.
Invarijanta predstavlja zbir pariteta permutacija svih 16 pločica i pariteta razlike između zbira kolona plus zbira redova i prazne pločice u donjem desnom uglu. Nepromenljiva je jer svaki pokret menja paritet permutacija i paritet razlike. Konkretno, ako je prazna pločica u donjem desnom uglu a broj permutacija je paran, slagalica je rešiva.
Vilson je 1974. godine proučavao analogiju između igre 15 pazli i proizvoljnih konačnih povezanih i nerazdvojivih grafova. Graf se smatra razdvojivim ukoliko uklanjanjem jednog čvora povećavamo broj komponenata. Pokazao je, osim za poligone i jedan posebni graf sa sedam čvorova, da je moguće dobiti sve permutacije osim ako je graf bipartitivan, i u tom slučaju samo parne permutacije mogu biti dobijene. Posebni graf sa sedam čvorova je regularni heksagon sa jednom dijagonalom i čvorom dodatim u centru. Samo jedna šestina permutacija može biti dobijena.
Za veće verzije ove pazle, pronalaženje rešenja je jednostavno, ali problem nalaženja najkraćeg rešenja je polinomijalne kompleksnosti. Za slučaj sa 15 pločica, dužine raspona optimalnih rešenja idu od 0 do 80 pomeranja jedne pločice, ili 43 pomeranja više pločica. Pazla sa 8 pločica može biti rešena u ne više od 31 pomeranja jedne pločice ili 24 pomeranja više pločica.[1][2] For the 15-puzzle, lengths of optimal solutions range from 0 to 80 single-tile moves[3] Broj mogućih početnih konfiguracija za pazle sa 24 pločice je 25!/2, što je previše da bi se odredio božji algoritam, kao i božji broj. Donja granica je određena 2011. godine i iznosi 152 pomeranja jedne pločice,[4] a gornja granica 208 pomeranja jedne pločice ili 109 pomeranja više pločica.[5][6] Simetrije 15 pazle formiraju grupoid (grupoid).[7][8]
U alternativnom pogledu problema, možemo razmotriti da je invarijanta zbir pariteta broja inverzija u trenutnom poretku 15 numerisanih pločica i pariteta razmaka između broja reda prazne pločice i broja reda poslednjeg reda. Ovo je nepromenljivo jer svako pomeranje u okviru iste kolone menja i broj pariteta broja inverzija (menjanjem broja inverzija za ±1, ±3...) i paritet razmaka od poslednjeg reda (±1). Svako pomeranje u okviru istog reda ne menja paritet. Ako pogledamo rešeno stanje zagonetke, zbir je paran. Samim tim, indukcijom je lako dokazati da bilo koje stanje pazle u kom je zbir neparan ne može biti rešeno. Konkretno, ako je prazna pločica u donjem desnom uglu ili čak bilo gde u poslednjem redu, pazla se može rešiti ako i samo ako je broj inverzija pločica sa brojem paran.
Zagonetku je izmislio Nojs Palmer Čapman, koji je 1874. godine u Kanastoti, u Njujorku prijateljima pokazao pazlu koja se sastojala od 16 pločica obeleženih brojevima, koje treba da se poređaju zajedno u redovima po četiri, pri čemu svaki red daje zbir do 34. Kopije ove pazle stigle su preko njegovog sina do Sirakuze u Njujorku, a odatle do Hartforda, Konektikat, gde su učenici Američke škole za gluve osobe počeli da ih prave, i već u decembru 1879. godine prodavali su ih lokalno i u Bostonu, Masačusets. Matijas Rajs, vlasnik prodavnice drvenih predmeta u Bostonu, zainteresovao se za ovu zagonetku i sam je počeo da ih pravi. U januaru 1880. godine, dr Čarls Pivi, zubar iz Masačusetsa, privukao je pažnju ponudivši novac onom ko može da je reši. Čapman je patentirao ovu igru 1880. godine. Iste godine igra je postala popularna u Sjedinjenim državama, Kanadi, Evropi, a u Japanu tek 1889. godine.[9]
Sem Lojdu se pripisuje nastanak slagalice, pogotovo jer je tvrdio da je on ustvari napravio ovu igru, i od 1891. godine do kraja života je pokušavao da patentira pronalazak. Te je to i napisano u enciklopediji pazli (Cyclopedia of Puzzles) objavljenoj 1914. godine:
Stariji stanovnici Pazlelenda će pamtiti kako sam tokom ranih sedamdesetih zaintrigirao ceo svet malom kutijom sa pomeralicama koje su kasnije postale poznate kao 14-15 pazle.
Međutim, Lojd nije ni u kom slučaju bio povezan sa inicijalnom popularnošću slagalica, jer je pomama za slagalicama počela 1880ih, a ne ranih 1870ih. Lojdov prvi članak o pazlama je bio objavljen 1886. da bi se tek 1891. godine on prvi put počeo predstavljati kao izumitelj slagalica.[9][10]
Lojd je kasnije privukao dodatnu pažnju tako što je ponudio 1000 dolara svakome ko bi mogao da ponudi rešenje „Lojdove kombinacije“, i da zameni pločice 14 i 15 koje u startu leže na zamenjenim pozicijama. Ovo je bilo nemoguće, što su deceniju ranije dokazali Džonson i Stori, s obzirom da se zamenom pločica desila transformacija iz parne u neparnu kombinaciju.
- ↑ Daniel Ratner, Manfred K. Warmuth. Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable. National Conference on Artificial Intelligence, 1986.
- ↑ Ratner, Daniel; Warmuth, Manfred (1990). „The (n2−1)-puzzle and related relocation problems”. Journal of Symbolic Computation 10 (2): 111–137. DOI:10.1016/S0747-7171(08)80001-6.
- ↑ A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, The parallel search bench ZRAM and its applications, Annals of Operations Research 90 (1999), str. 45–63.
- ↑ "24 puzzle new lower bound: 152". Domain of the Cube Forum
- ↑ "5x5 can be solved in 109 MTM". Domain of the Cube Forum.
- ↑ "m × n puzzle (current state of the art)" Arhivirano 2016-03-07 na Wayback Machine-u. Sliding Tile Puzzle Corner.
- ↑ The 15-puzzle groupoid (1), Never Ending Books
- ↑ The 15-puzzle groupoid (2), Never Ending Books
- ↑ 9,0 9,1 The 15 Puzzle, by Jerry Slocum & Dic Sonneveld, 2006. ISBN 1-890980-15-3
- ↑ Barry R. Clarke, Puzzles for Pleasure, str.10-12, Cambridge University Press, 1994 ISBN 0-521-46634-2.
