Problem S. 24. (February 2007)

S. 24. In this exercise we consider knight's tours on the usual chessboard (that is, the knight visits every square exactly once). For each square as initial position, you should give the number of different tours. (Two tours are different, if the squares are visited in a different order.)

The output is written as an 8×8 table on the standard output. The source code of your solution (s24.cpp, s24.pas, ) and a short documentation (s24.txt, s24.pdf) should be submitted.

(10 pont)

Deadline expired on March 19, 2007.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

4 students sent a solution.
10 points:	Kezes Balázs.
6 points:	1 student.
5 points:	2 students.

Problems in Information Technology of KöMaL, February 2007