假设国际象棋棋盘有 5*5 共 25 个格子。
设计一个程序，使棋子从初始位置（棋盘编号为 1 的位）开始跳马，能够把棋盘的格子全部都走一遍，每个格子只允许走一次。
输出一个如图 2 的解，左上角为第一步起点。
总共有多少解。
PS：国际象棋的棋子是在格子中间的。国际象棋中的“马走日”，如下图所示，第一步为[1,1],
第二步为[2,8]或[2,12]，第三步可以是[3,5]或[3,21]等，以此类推。
答案：
明确函数功能：jump(m, n)为跳到(m, n)位置。
寻找递归出口：不在边界之内 或 已走过。
明确所有路径：8个方位，
技巧：这里可以用一个数组存入八个方位的变化，再用循环依次取出，比写八个方位要聪明许多。
回溯还原现场：
path--; // 回溯法关键步骤
a[m][n] = 0;
//马走日
class Sy2 {
private static int[][] next = { { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }, { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 } }; // 马的跳跃路径（技巧）
private static int[][] map; // 地图
private static int m, n;
private static int count = 0;// 统计有多少种走法
private static int step = 0;
public static void main(String[] args) {
m = 5;
n = 5;
int x = 0;
int y = 0;
map = new int[m][n];
jump(x, y);
System.out.println("---------");
System.out.println(count);
}
private static void jump(int x, int y) {
// 如果超出界限，那就继续下一轮
if (x < 0 || x >= m || y < 0 || y >= n || map[x][y] != 0) {
return;
}
// 立足此节点
step++;
map[x][y] = step;
if (step == m * n) {
if (count == 0) // 如果是第一次，那就输出一个
show(map);
count++;
}
// 写出所有路径（技巧）
int tx = 0, ty = 0;
for (int i = 0; i < 8; i++) {
tx = x + next[i][0]; // 技巧
ty = y + next[i][1];
jump(tx, ty);
}
// 还原
step--;
map[x][y] = 0;
}
// 显示数组
private static void show(int[][] arr) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
System.out.print(arr[i][j] + " \t");
}
System.out.println();
}
}
}
程序运行结果：
八皇后
编程解决“八皇后问题”：即 在一个 8*8 的矩形格子中排放 8 个皇后。
要满足的条件包括：任意两个皇后不能在同一行，同一列，也不能在同一条对角线上。
要求编程给出解的个数。
答案：
算法原理：回溯法
首先，可归纳问题的条件为，8 皇后之间需满足：
不在同一行上
不在同一列上
不在同一斜线上
不在同一反斜线上
