KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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, \ldots) and a short documentation (s24.txt, s24.pdf) should be submitted.

(10 pont)

Deadline expired on 19 March 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.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley