亲宝软件园·资讯

展开

Java马踏棋盘

L_Mcode 人气:0

马踏棋盘很好实现,但有时运行起来特别慢,还可能出不来结果,最常用的就是深度优先遍历+回溯,相信大家都学过数据结构,对图的深度遍历都有了解,下面就是代码的实现,如果对代码理解有困难,可以先熟悉一下图的深度优先遍历

大家可以把棋盘改小一些测试,8x8的确实很慢

import java.util.Arrays;

/**
 * 骑士周游问题
 * @author LM_Code
 * @create 2019-03-17-18:57
 */
public class KnightProblem {
    static final int SIZE = 8;//设置棋盘的行数和列数>=5时才有解
    static final int[][] A = new int[SIZE][SIZE];//初始化棋盘,数组中所有值默认为0
    static final int[] NEXT= new int[]{1, 2};//设置马的下一步,用空间为2的数组代替x,y坐标
    public static void main(String[] args) {
        //判断此点是否能走完整个棋盘
        if(method(NEXT, 1)){//能,则输出棋盘轨迹
            for (int i = 0; i < A.length; i++) {
                System.out.println(Arrays.toString(A[i]));
            }
        }else{//不能,提示无解
            System.out.println("此起点无解");
        }
    }
    //传入下一步NEXT,和并表明下一步是第几步tag,返回此点是否能走完棋盘(有解)
    public static boolean method(int[] NEXT, int tag){
        int[] current = new int[]{NEXT[0], NEXT[1]};//将当前步存入本次方法调用的局部变量
        A[current[0]][current[1]] = tag;//把马跳到当前位置,并标记为是第几步
        // 如果是最后一步,递归结束
        if(tag == SIZE*SIZE){
            return true;
        }
        //如果不是最后一步,下一步有8中可能
        for (int i = 0; i < 8; i++) {
            //下一步的第i种情况是否可走
            if(canGo(current, i)){//如果可以走,继续递归
                //判断此时的下一步,是否能走完棋盘
                if(method(NEXT, tag+1)){//能,返回true,递归结束
                    return true;
                }
                //此时的下一步不能走完棋盘,则继续寻找第i+1种情况的下一步是否有解
            }
            //此时的下一步无解,则寻找第i+1种情况是否有解
        }
        //如果当前步无法走完棋盘(无解)
        A[current[0]][current[1]] = 0;//回溯:撤销当前步,当前步赋值为0
        return false;//返回false,回到上一步,表明此步无解
    }
    //判断下一步是否能走,下一步有8中情况0-7,传入当前步arr,判断是否有第count种情况的下一步
    public static boolean canGo(int[] arr,int count){
        switch (count){
            case 0 :
                if(arr[0]-1>=0&&arr[1]+2<SIZE&&A[arr[0]-1][arr[1]+2]==0) {
                    NEXT[0] = arr[0]-1;
                    NEXT[1] = arr[1]+2;
                    return true;
                }
                break;
            case 1 :
                if(arr[0]+1<SIZE&&arr[1]+2<SIZE&&A[arr[0]+1][arr[1]+2]==0){
                    NEXT[0] = arr[0]+1;
                    NEXT[1] = arr[1]+2;
                    return true;
                }
                break;
            case 2 :
                if(arr[0]+2<SIZE&&arr[1]+1<SIZE&&A[arr[0]+2][arr[1]+1]==0){
                    NEXT[0] = arr[0]+2;
                    NEXT[1] = arr[1]+1;
                    return true;
                }
                break;
            case 3 :
                if(arr[0]+2<SIZE&&arr[1]-1>=0&&A[arr[0]+2][arr[1]-1]==0){
                    NEXT[0] = arr[0]+2;
                    NEXT[1] = arr[1]-1;
                    return true;
                }
                break;
            case 4 :
                if(arr[0]+1<SIZE&&arr[1]-2>=0&&A[arr[0]+1][arr[1]-2]==0){
                    NEXT[0] = arr[0]+1;
                    NEXT[1] = arr[1]-2;
                    return true;
                }
                break;
            case 5 :
                if(arr[0]-1>=0&&arr[1]-2>=0&&A[arr[0]-1][arr[1]-2]==0){
                    NEXT[0] = arr[0]-1;
                    NEXT[1] = arr[1]-2;
                    return true;
                }
                break;
            case 6 :
                if(arr[0]-2>=0&&arr[1]-1>=0&&A[arr[0]-2][arr[1]-1]==0){
                    NEXT[0] = arr[0]-2;
                    NEXT[1] = arr[1]-1;
                    return true;
                }
                break;
            case 7 :
                if(arr[0]-2>=0&&arr[1]+1<SIZE&&A[arr[0]-2][arr[1]+1]==0){
                    NEXT[0] = arr[0]-2;
                    NEXT[1] = arr[1]+1;
                    return true;
                }
                break;
            default:
        }
        return false;
    }
}

加载全部内容

相关教程
猜你喜欢
用户评论