Igra 15 pazli
<s>Igra 15 pazli () 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.</s><s>Ova slagalica postoji i u drugim veličinama, poput manje "igre 8 pazli".</s><s>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".</s>

<s>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.</s><s>Ova igra predstavlja klasičan problem modelovanja algoritma koji koristi heuristiku.</s><s>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.</s>

<s>Rešivost 
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.</s><s>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.</s>

<s>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.</s><s>Nepromenljiva je jer svaki pokret menja paritet permutacija i paritet razlike.</s><s>Konkretno, ako je prazna pločica u donjem desnom uglu a broj permutacija je paran, slagalica je rešiva.</s>

<s>Vilson je 1974. godine proučavao analogiju između igre 15 pazli i proizvoljnih konačnih povezanih i nerazdvojivih grafova.</s><s>Graf se smatra razdvojivim ukoliko uklanjanjem jednog čvora povećavamo broj komponenata.</s><s>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.</s><s>Posebni graf sa sedam čvorova je regularni heksagon sa jednom dijagonalom i čvorom dodatim u centru.</s><s>Samo jedna šestina permutacija može biti dobijena.</s>

<s>Za veće verzije ove pazle, pronalaženje rešenja je jednostavno, ali problem nalaženja najkraćeg rešenja je polinomijalne kompleksnosti.</s><s>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.</s><s>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.</s><s>For the 15-puzzle, lengths of optimal solutions range from 0 to 80 single-tile moves 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.</s><s>Donja granica je određena 2011. godine i iznosi 152 pomeranja jedne pločice, a gornja granica 208 pomeranja jedne pločice ili 109 pomeranja više pločica.</s><s>Simetrije 15 pazle formiraju grupoid (grupoid).</s>

<s>Alternativni dokaz 
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.</s><s>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).</s><s>Svako pomeranje u okviru istog reda ne menja paritet.</s><s>Ako pogledamo rešeno stanje zagonetke, zbir je paran.</s><s>Samim tim, indukcijom je lako dokazati da bilo koje stanje pazle u kom je zbir neparan ne može biti rešeno.</s><s>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.</s>

<s>Istorija</s>

<s>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.</s><s>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.</s><s>Matijas Rajs, vlasnik prodavnice drvenih predmeta u Bostonu, zainteresovao se za ovu zagonetku i sam je počeo da ih pravi.</s><s>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.</s><s>Čapman je patentirao ovu igru 1880. godine.</s><s>Iste godine igra je postala popularna u Sjedinjenim državama, Kanadi, Evropi, a u Japanu tek 1889. godine.</s>

<s>Sem Lojd</s>

<s>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.</s><s>Te je to i napisano u enciklopediji pazli (Cyclopedia of Puzzles) objavljenoj 1914. godine:</s>

<s>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.</s><s>Lojdov prvi članak o pazlama je bio objavljen 1886. da bi se tek 1891. godine on prvi put počeo predstavljati kao izumitelj slagalica.</s>

<s>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.</s><s>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.</s>

<s>Vidi još 
 Rubikova kocka
 Enigmatika
 Problem misionara i kanibala</s>

<s>Reference</s>

<s>Spoljašnje veze</s>

<s>hc11.home.xs4all.nl/15puzzle/15puzzen.html
 hessandpoker.com/fifteen-puzzle-solution.html
 cubezzz.duckdns.org/drupal/?q=node/view/238/2557#comment-2557
 cubezzz.duckdns.org/drupal/?q=node/view/241/2566#comment-2566</s>

<s>Enigmatika
Igre</s>

