Problem S. 55. (September 2010)

S. 55. It is well known that one knight can visit each square of the chessboard such that each square is touched exactly once. (There is an easy algorithm for this.) Your task is now a little harder: the first few steps are already done.

Your program should find the longest possible completion of this path. The first command line argument of your program is the name of the file containing the steps already taken. The second command line argument is the name of the file where the rest of the path should be written. Both files have the same structure: the first line contains the number of steps (\(\displaystyle L\)) already taken, and the second line contains names of the \(\displaystyle L\) fields with the actual steps, separated by spaces.

The example shows a possible beginning.

Remarks:

[] The size of the chessboard is 6x6, fields are denoted as usual.

[] The of the input file is the same as the first square of the output file.

[] If the path can not be continued, a character ``1'' should be written in first line, and the second line should contain the actual position of the knight.

The source code and project files of your solution -- without the .exe or any other auxiliary files generated by the compiler -- should be submitted together with a short documentation (s55.txt, s55.pdf, ...) in a compressed folder s55.zip.

(10 pont)

Deadline expired on October 11, 2010.

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

A beküldők többsége helyesen ismerte fel, hogy a backtrack algoritmust kell használni a megoldáshoz, mivel a maximális lépésszámot kerestük. A lényeg dióhéjban: - az eddig bejárt mezőket foglaltnak jelöljük - az utolsó pozícióból megpróbálunk továbblépni (a lehetséges "irányokkal" rögzített sorrendben próbálkozunk) - ha egy adott pozícióból nem vezet tovább út, akkor - ha a hozzá tartozó lépésszám maximális - az utat mentjük és visszalépünk az előző mezőre, ahonnan a következő iránnyal próbálkozunk. - a program befejeződik az összes lehetséges út bejárásakor, valamint akkor is, ha találtunk egy 36 lépés hosszú utat.

Sokan a kódolást is hiba nélkül végezték, a legtöbb program a legtöbb tesztesetre egy-két másodperc alatt lefutott.

A következő teszteseteket használtuk az értékelés során:

- csak egy mezőn jártunk (be1) - 6 mezőt érintettünk, a tábla teljesen bejárható (be8) - 18 mezőt érintettünk, a tábla teljesen bejárható (be3)

- a táblát teljesen bejártuk, nincs továbblépésre mód (be2) - az út nem folytatható (be6)

- 12 mezőt érintettünk, a tábla nem járható be, de folytatható (be5) - 18 mezőt érintettünk, a tábla nem járható be, de folytatható (be4) - 25 mezőt érintettünk, a tábla nem járható be, de folytatható (be7)

A tesztesetek: s55teszt.zip

Sok hibátlanul működő megoldás született, az egyik legtömörebb megoldást Boros Zalán adta: s55borsos.cpp

Egy lehetséges kimenet: s55kimenet.zip

Statistics:

17 students sent a solution.
10 points:	Adrián Patrik, Barta 111 János, Borsos 607 Zalán, Fekete 976 János, Mihálykó András, Nagy 111 Miklós.
9 points:	Élő Dániel, Nagy Róbert, Paczolay Gábor, Weisz Gellért.
8 points:	2 students.
7 points:	1 student.
6 points:	1 student.
4 points:	1 student.
1 point:	1 student.
0 point:	1 student.

Problems in Information Technology of KöMaL, September 2010