Posted By: Aldar (posledni mohykan) on 'CZriddles'
Title:     Re: Lloydova patnactka
Date:      Fri Mar 27 19:06:40 1998

> Tak to kriterium resitelnosti uz vime... Je to vice mene znamenko
> permutace, bez 0 (prazdneho policka) (jednoduse se presoupa do pozice 
> [4;4]) A znamenko se vypocita takto:
> 
> (-1)^(pocet inverzi)
> (-1)^(pocet cyklu liche delky)
> (-1)^(transpozic)
> 

inverze:
 Usporadame-li prvky X do posloupnosti (1,2,...,n) (kde n je pocet prvku X). 
 muzeme permutaci znazornit tabulkou
     p(1)   p(2)   P(3)   .... p(n)
      ^      ^      ^      ^    ^
      |      |      |      |    |
      1      2      3     ....  n

 Kazdou dvojici i<j, kde p(i)>p(j) nazveme inverzi tabulky (permutace)
 pozn.: to je vlastne to, co tady vise popisoval Xofon...

cyklus:
 Jakoukoliv usporadanou n-tici (x1,x2,...,xn), pokud p(xi)=p(xi+1) pro 
 i=1,..,n-1 a p(xn)=x1 nazveme cyklem permutace p delky n-1
 jinymi slovy:

  "cilova" permutace            zjistujeme cyklus
   /---------------            /---------------
   | 1 | 2 | 3 | 4 |            | 5 | 1 | 2 | 4 |
   -----------------            -----------------
   | 5 | 6 | 7 | 8 |            | 7 | 6 | 3 | 8 |
   -----------------            -----------------
   | 9 |10 |11 |12 |            | 9 |10 |11 |12 |
   -----------------            -----------------
   |13 |14 |15 |   |            |13 |14 |15 |   |
   ---------------/            ---------------/

takze zjistime delku cyklu na [1;1], je tam c. 5, na miste petky je 7, na
miste sedmicky je 3jka, na miste 3 je 2, na miste 2 je 1 a na miste 1 je zase 5
 5->7->3->2->1-> 5->.....
 takze mame cyklus delky 4, coz je sude cislo, takze se nezapocitava... jiny 
 cyklus tam neni, takze to nema reseni... 

transpozice:
 permutaci p : X -> X bude transpozice, existuje-li x<>y z X tak, ze p(x)=y,
 p(y)=x a jinak p(z)=z pro z z X-{x,y}
 jinymi slovy: pokud soupneme prazne policko, tak udelame 1 transpozici
 nebo taky, pokud prohodime kterekoliv 2 policka...

> > Ale jinak:
> >   Nevite nekdo, kdyz uz vim, ze to ma reseni, kolik je maximalni odhad
> > poctu tahu k vyreseni? Urcite je to podstatne mensi cislo, nez pocet 
> > vsech stavu, ktere vedou k reseni (n!/2 ; n=16). Nejak to vychazi na cca 
> > 50...
>  Jak to myslis? Maximalni odhad. Nemas na mysli odhad minimalniho poctu tahu
> pri znamem zadani?

Slo mi o to, ze pri hledani reseni prohledavanim do hloubky staci hledat do 
nejake max. urovne, reseni by melo byt nad ni (samozrejme, pokud hledame 
nejake optimalnejsi a nestaci nam prohledavani do hloubky s nejakym 
algoritmem, dokud nenarazime na reseni...(vetsinou to byva takovych 30000 tahu 
;-))

>                                Alnagon
> 
>         <Lepe, kdyz se certi zeni, nez kdyz se zeny certi>

Doufam, ze to bylo srozumitelne... takovy drobny vytazek z algebry... tento 
post mel aspon jednu vyhodu, konecne jsem se to naucil... :-)

Cuz

                                      Aldar