思路： 正常回溯算法，通过贪心算法优先走剩余可走位置少的，因为可能之后再也走不到了
代码：
package com.wangyq.datastructrue.arithmetic; import java.util.Arrays; /** * 回溯算法，贪心算法实现马踏棋盘问题 */ public class TheHorseStepBoard { static final int[] dx = {-2, -1, 1, 2, 2, 1, -1, -2}; // x方向的增量 static final int[] dy = {1, 2, 2, 1, -1, -2, -2, -1}; // y方向的增量 static int[][] checkerboard = null; static int checkerboardSize = 8; static int[][] test = new int[checkerboardSize][checkerboardSize]; // static int stepNUM = 0; public static void main(String[] args) { checkerboard = new int[checkerboardSize][checkerboardSize]; theHorseStepBoard(2, 3, 1); int i = 0; System.out.println("没有方案可以实现"); } private static void theHorseStepBoard(int x, int y, int stepNUM) { //标记当前节点走过 checkerboard[x][y] = 1; if (stepNUM == 64) { show(); System.exit(0); } //记录可行走下一步各个节点可走位置数量 int[] nextCount = new int[checkerboardSize]; for (int i = 0; i < checkerboardSize; i++) { int tempX = x + dx[i]; int tempY = y + dy[i]; //获取下一步可走的 if (tempX >= 0 && tempY >= 0 && tempX < checkerboardSize && tempY < checkerboardSize && checkerboard[tempX][tempY] == 0) { nextCount[i] = getCount(tempX, tempY); } } //对数量进行排序，确定可走路径的执行顺序 int[] next = sort(nextCount); for (int i = 0; i < checkerboardSize; i++) { if (next[i] != 0) { int tempX = x + dx[next[i] - 1]; int tempY = y + dy[next[i] - 1]; //记录行走路径 test[tempX][tempY] = stepNUM; theHorseStepBoard(tempX, tempY, stepNUM + 1); //没有走通，重置节点状态 checkerboard[tempX][tempY] = 0; } } return; } /** * 打印行走路径 */ private static void show() { for (int i = 0; i < checkerboardSize; i++) { System.out.println(Arrays.toString(test[i])); } } private static int[] sort(int[] nextCount) { int[] next = new int[checkerboardSize]; for (int i = 0; i < checkerboardSize; i++) { if (nextCount[i] != 0) { next[i] = i + 1; } } int index; int temp; //这里用的选择排序 for (int i = 0; i < checkerboardSize; i++) { index = i; for (int j = i + 1; j < checkerboardSize; j++) { if (nextCount[index] > nextCount[j]) index = j; } if (i != index) { temp = nextCount[i]; nextCount[i] = nextCount[index]; nextCount[index] = temp; //同步调整下一步行走位置的顺序 temp = next[i]; next[i] = next[index]; next[index] = temp; } } return next; } /** * 获取该位置还有几个位置可走 * * @param x * @param y * @return */ private static int getCount(int x, int y) { //返回下一次的xy //防止与0角标混，所以先加1 int count = 1; for (int i = 0; i < checkerboardSize; i++) { int tempX = x + dx[i]; int tempY = y + dy[i]; if (tempX >= 0 && tempY >= 0 && tempX < checkerboardSize && tempY < checkerboardSize && checkerboard[tempX][tempY] == 0) { count++; } } return count; } }运行结果： [47, 14, 29, 32, 1, 16, 21, 24] [30, 33, 46, 15, 28, 23, 2, 17] [13, 48, 31, 0, 43, 20, 25, 22] [34, 45, 42, 49, 58, 27, 18, 3] [51, 12, 63, 44, 19, 40, 57, 26] [62, 35, 50, 41, 54, 59, 4, 7] [11, 52, 37, 60, 9, 6, 39, 56] [36, 61, 10, 53, 38, 55, 8, 5]
