算法实现题 6-19 骑士征途问题
«问题描述:
在一个 n*n 个方格的国际象棋棋盘上,马(骑士)从任意指定方格出发,按照横 1 步竖
2 步,或横 2 步竖 1 步的跳马规则,走遍棋盘的每一个格子,且每个格子只走 1 次。这样的
跳马步骤称为 1 个成功的骑士征途。例如,当 n=5 时的 1 个成功的骑士征途如下图所示。
1 2 3 4 5
1 25 14 1 8 19
2 4 9 18 13 2
3 15 24 3 20 7
4 10 5 22 17 12
5 23 16 11 6 21
«编程任务:
对于给定的 n 和 n*n 方格的起始位置 x 和 y。用分支限界法找出从指定的方格(x,y)出发
的一条成功的骑士征途。
«数据输入:
由文件 input.txt 给出输入数据。第一行有 1 个正整数 n (1≤n≤10);第二行有 2 个正整
数 x 和 y,表示骑士的起始位置为(x,y)。
«结果输出:
将计算出的成功骑士征途输出到文件 output.txt。如果不存在从(x,y)出发的成功的骑士征
途则输出’No Solution!’。
输入文件示例 输出文件示例
input.txt output.txt
5
1 3
25 14 1 8 19
4 9 18 13 2
15 24 3 20 7
10 5 22 17 12
23 16 11 6 21