Az S. 24. feladat (2007. február)

S. 24. A 8×8-as sakktáblát bejárjuk lóugrásban úgy, hogy minden mezőt pontosan egyszer érintünk. Adjuk meg a sakktábla minden egyes mezőjére, hogy onnan kiindulva hány különböző bejárás létezik. Két bejárást akkor tekintünk különbözőnek, ha abban a mezők bejárási sorrendje eltér.

A program az eredményt a standard kimenetre írja a sakktáblának megfelelő 8×8-as táblázat formájában.

Beküldendő a megoldást adó program forrásállománya (s24.cpp, s24.pas, ), illetve rövid dokumentációja (s24.txt, s24.pdf).

(10 pont)

A beküldési határidő 2007. március 19-én LEJÁRT.

A feladatot például visszalépéses kereséssel ügyesen meg lehet oldani. Sajnos belátható időn belül nem fog lefutni a program 8x8-as sakktáblára, ezért érdemes a tábla méretét paraméterként fölvenni.

4x4-es, vagy annál kisebb táblán egyik mezőről indulva sincs megfelelő bejárás. 5x5-ös és 6x6-os táblán az egyes mezőkről indulva már kapunk megoldásokat néhány perc, illetve néhány óra alatt.

Mivel a sakktábblának több szimmetriatengelye is van, ezért nem kell az összes mezőről elindítani a huszárt. Így például 6x6-os tábla esetén (0,0)-tól (5,5)-ig sorszámozva a tábla mezőit a bejárások száma a következő: (0,0)-ról indulva 524486, (0,1)-ről indulva 289050 (0,2)-ről indulva 115837 (1,1)-ről indulva 173402 (1,2)-ről indulva 49578 (2,2)-ről indulva 52662 (0,3)-ról indulva 115837 (1,3)-ról indulva 49578 (2,3)-ról indulva 52662 (3,3)-ról indulva 52662 bejárást kapunk.

A megoldás C++ nyelven: s24mo.cpp.

Statisztika:

4 dolgozat érkezett.
10 pontot kapott:	Kezes Balázs.
6 pontot kapott:	1 versenyző.
5 pontot kapott:	2 versenyző.

A KöMaL 2007. februári informatika feladatai