了解了八皇后问题之后我们再来看一下大同小异的马走日问题。
问题描述：在n*m的棋盘中，马只能走"日"字。马从位置(x,y)出发，把棋盘的每一格都走一次且只走一次。找出所有路径。
我们以5*4为例，还是将每个格子都标上数字。每个数字都是两位，十位数字表示该格子所在的行，而个位数字表示该格子所在的列。
这个问题同样是两个限制条件：1.每一个格子都走，且每个格子只走一次。2.必须走日字
那么什么情况算是走了日字呢？有什么规律吗？
1.左下右上横日字跳法（起始方格与终止方格数字之差为8）
2.左上右下横日字跳法（起始方格与终止方格数字之差为12）
3.左下右上竖日字跳法（起始方格与终止方格数字之差为19）
4.左上右下竖日字跳法（起始方格与终止方格数字之差为21）
限制条件找到了，我们还是找“马”的存储结构，这里我们依然选择一维数组：因为每个格子只能走一次，所以也符合一维数组的存储特性，即一个索引对应一个元素。
python实现：
while True: arr1 = [] n = int(input("棋盘行数：")) #输入行数 m = int(input("棋盘列数：")) #输入列数 xx = int(input("起始行标：")) #输入起始行标号 yy = int(input("起始列标：")) #输入起始列标号 for x in range(n): for y in range(m): a = 10*x+y #通过行列转换成方格中的数字 arr1.append(a) num = 0 def horse(arr,finish_line=1): arr[0] = xx*10+yy #通过起始位置的行列标号转换成起始位置方格中的数字 flag = True if finish_line == len(arr): global num num += 1 print("第%s种走法：" %num) for i in arr: #将方格中的元素转化为下标的形式输出 mm = str(int(i/10)) nn = str(int(i%10)) print("("+mm+","+nn+")") # print(arr) return 0 for stand in arr1: #保证马一直在棋盘范围内活动 arr[finish_line] = stand # print(arr) if finish_line >= 1: #从初始位置的下一个位置判断是否与上一个位置成日字 if abs(arr[finish_line] - arr[finish_line - 1]) != 8 and abs(arr[finish_line] - arr[finish_line - 1]) != 12 and abs(arr[finish_line] - arr[finish_line - 1]) != 19 and abs(arr[finish_line] - arr[finish_line - 1]) != 21: flag = False else: flag = True for line in range(finish_line): if arr[finish_line] == arr[line]: #判断当前位置之前是否被走过 flag = False if flag == True: horse(arr,finish_line+1) if __name__ == '__main__': horse([None]*n*m) print(" 一共%s种走法" %num)
JAVA实现：
import java.util.Scanner; import java.util.Arrays; public class horse { public static int num=0; // public static int []arr1 = new int[20]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); //初始化的输入操作 System.out.println("棋盘高："); int height = sc.nextInt(); System.out.println("棋盘宽："); int width = sc.nextInt(); System.out.println("起始横坐标："); int startx = sc.nextInt(); System.out.println("起始纵坐标："); int starty = sc.nextInt(); int []arr = new int[height*width]; int []arr1 = new int[height*width]; //arr1列表用来存放所有格子，同时保证了出界的问题 int i=0; for(int x=0; x<height; x++){ for(int y=0; y<width;y++){ arr1[i++]=10*x+y; } } System.out.println(Arrays.toString(arr1)); arr[0] = 10*startx+starty; int finish_index = 1; int node_num = height*width; horse_ri(arr,arr1,finish_index); System.out.printf("共%d种走法",num); } static void horse_ri(int arr[],int arr1[],int finish_index){ boolean flag=true; if(finish_index==arr.length){ num++; System.out.printf("第%d种走法",num); System.out.println(Arrays.toString(arr)); return; } for(int ind=1;ind<arr1.length; ind++){ arr[finish_index]=arr1[ind]; flag = true;
//不是日字的情况 if((Math.abs(arr[finish_index]-arr[finish_index-1])!=8)&&(Math.abs(arr[finish_index]-arr[finish_index-1])!=12)&&(Math.abs(arr[finish_index]-arr[finish_index-1])!=19)&&(Math.abs(arr[finish_index]-arr[finish_index-1])!=21)){ flag = false; }
//之前走过的格子 for(int index=0;index<finish_index;index++){ if(arr[finish_index]==arr[index]){ flag = false; } } if(flag==true){ horse_ri(arr,arr1,finish_index+1); } } } }