马踏棋盘（骑士周游问题）JAVA

马踏棋盘问题

马踏棋盘问题是旅行商问题（TSP）或哈密顿回路问题（HCP）的一个特例。在 8×8 的国际象棋棋盘上，用一个马按照马步跳遍整个棋盘，要求每个格子都只跳到一次，最后回到出发点。这是一个 NP问题，通常采用回溯法或启发式搜索类算法求解。在 9×10 的中国象棋棋盘上也可以实现马步遍历。

在这篇文章介绍的是递归加贪心来实现骑士周游问题（图是我学习时方便记录所截的图）

总得来说就是通过递归来一直获取下一步可以走的位置并记录下已走过的节点，最后通过已走的步数和是否走完来棋盘（此路不通便可或者已找到方案）来作为回溯触发条件如果已找到走完棋盘的路就退出。

贪心就体现在对已获取下一步节点位置的节点位置的可走步数实现排序从小到大以此来优化算法

如果没有贪心便只能通过改变查找下一步时的策略来进行优化(策略不同所花费的时间也会有很大差别)

 话不多说直接上代码(具体步骤的作用都有注释)

import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

//马踏棋盘（骑士周游问题）(递归回溯)+贪心
public class DiGuiHorsePedalChessboardDemo {
    private static int X;//行
    private static int Y;//列
    private static boolean visited[];//记录已走过的节点（x*X+Y）
    private static boolean finished;//用来查看是否找到踏满棋盘的方法

    public static void main(String[] args) {
        X=8;Y=8;
        int row=41;
        int column=1;
        int[][]chess=new int[X][Y];
        visited=new boolean[X*Y];
        long start=System.currentTimeMillis();
        HorsePedalChessboard(chess,row-1,column-1,1);
        long end=System.currentTimeMillis();
        System.out.println(end-start);//输出耗时
        for (int[]r:chess) {
            System.out.println(Arrays.toString(r));//输出棋盘的走法
        }
    }

    
    public static ArrayList next(Point curPoint){//获取下一步所走的节点位置(因为通过贪心进行排序所以在此的策略便不是很重要)
        ArrayList ps = new ArrayList<>();
        Point p1=new Point();
        if((p1.x=curPoint.x-2)>=0&&(p1.y=curPoint.y-1)>=0){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x-2)>=0&&(p1.y=curPoint.y+1)=0){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x+2)=0&&(p1.y=curPoint.y-2)>=0){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x-1)>=0&&(p1.y=curPoint.y+2)=0){
            ps.add(new Point(p1));
        }
        if((p1.x=curPoint.x+1) ps=next(new Point(column,row));
        sort(ps);
        while (!ps.isEmpty()){
            Point p=ps.remove(0);
            if(!visited[p.y*X+p.x]){
                HorsePedalChessboard(chess,p.y,p.x,step+1);
            }
        }
        if(step ps){//排序判断的过程
        ps.sort(new Comparator() {
            @Override
            public int compare(Point o1, Point o2) {//根据当前节点的下一步的可走方案的大小来排序
                int count1=next(o1).size();
                int count2=next(o2).size();
                if(count1 

                
        
        

  
    
      
        
      
      
        
          暑期编程PK赛
          
        
        得CSDN机械键盘等精美礼品！