java中的回溯法问题的详细代码

实现：

复制代码
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 = 10x+y #通过行列转换成方格中的数字
arr1.append(a)
num = 0
def horse(arr,finish_line=1):
arr[0] = xx10+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+")")

//代码效果参考：http://www.zidongmutanji.com/bxxx/18370.html

        # 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[heightwidth];
int []arr1 = new int[heightwidth]; //arr1列表用来存放所有格子，同时保证了出界的问题
int i=0;
for(int x=0; x<height; x++){
for(int y=0; y<width;y++){
arr1[i++]=10*x+y;
}
}
//代码效果参考：http://www.zidongmutanji.com/bxxx/266022.html

    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);
         }
     }
}

}