The jumping knight P43694
You have a n × n board, where each position is permitted or prohibited. Given the initial position of a knight, you must determine if it is possible that the knight passes exactly once in each permitted position, doing the jumps of chess (that is, increasing or decreasing one of the dimensions in a unit, and the other dimension in two units).
Input
Input consists of a natural 3 ≤ n < 10, followed by n lines with n characters each one: a ’*’ indicates a prohibited position, a dot indicates a permitted position. Finally, a pair of integer numbers r and c between 1 and n indicates the initial row and column of the knight; the corner on the top and on the left is (1, 1). The initial position of the knight will never be prohibited.
Output
Your program must print a path of the knight for all the permitted position following the format of the instances. Notice that each position for which the knight passes is marked with two digits (being the first digit a 0 if it is needed), starting in 01 and increasing.
If there are more than a possible path, choose one of them. If the is not any possible solution, your program must print "no sol".
Input
4 .... .... .... ...* 4 1
Output
10 15 06 03 07 04 09 12 14 11 02 05 01 08 13 **
Input
5 ...*. .*... ....* .*... *..*. 3 2
Output
02 13 18 ** 04 19 ** 03 08 17 14 01 12 05 ** 11 ** 07 16 09 ** 15 10 ** 06
Input
3 ... ... ... 1 1
Output
no sol
- Author
- Salvador Roura
- Language
- English
- Translator
- Carlos Molina
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++