基於Java實現馬踏棋盤遊戲演演算法

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