Posted By: Aldar (posledni mohykan) on 'CZriddles'
Title:     Re: Lloydova patnactka
Date:      Fri Mar 27 11:17:22 1998

Jo, spravne, Lloydova patnactka... sorry...

> 
>  /---------------
>  | 1 | 2 | 3 | 4 |
>  -----------------
>  | 5 | 6 | 7 | 8 |
>  -----------------
>  | 9 |10 |11 |12 |
>  -----------------
>  |13 |14 |15 |   |
>  ---------------/
> 

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)

(muzu se rozepsat, jestli to nekoho zajima, co jsou to inverze, cykly+jejich 
delka, prip. transpozice...) 

Pokud vyjde -1, tak to nema reseni, jinak jo...


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

Dikec
                                      Aldar

Search the boards