import java.util.Arrays;

/**
?* 騎士周游問題
?* @author LM_Code
?* @create 2019-03-17-18:57
?*/
public class KnightProblem {
? ? static final int SIZE = 8;//設(shè)置棋盤的行數(shù)和列數(shù)>=5時才有解
? ? static final int[][] A = new int[SIZE][SIZE];//初始化棋盤，數(shù)組中所有值默認(rèn)為0
? ? static final int[] NEXT= new int[]{1, 2};//設(shè)置馬的下一步，用空間為2的數(shù)組代替x，y坐標(biāo)
? ? 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]};//將當(dāng)前步存入本次方法調(diào)用的局部變量
? ? ? ? A[current[0]][current[1]] = tag;//把馬跳到當(dāng)前位置，并標(biāo)記為是第幾步
? ? ? ? // 如果是最后一步，遞歸結(jié)束
? ? ? ? if(tag == SIZE*SIZE){
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? //如果不是最后一步，下一步有8中可能
? ? ? ? for (int i = 0; i < 8; i++) {
? ? ? ? ? ? //下一步的第i種情況是否可走
? ? ? ? ? ? if(canGo(current, i)){//如果可以走，繼續(xù)遞歸
? ? ? ? ? ? ? ? //判斷此時的下一步，是否能走完棋盤
? ? ? ? ? ? ? ? if(method(NEXT, tag+1)){//能，返回true，遞歸結(jié)束
? ? ? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? //此時的下一步不能走完棋盤，則繼續(xù)尋找第i+1種情況的下一步是否有解
? ? ? ? ? ? }
? ? ? ? ? ? //此時的下一步無解，則尋找第i+1種情況是否有解
? ? ? ? }
? ? ? ? //如果當(dāng)前步無法走完棋盤（無解）
? ? ? ? A[current[0]][current[1]] = 0;//回溯：撤銷當(dāng)前步，當(dāng)前步賦值為0
? ? ? ? return false;//返回false，回到上一步，表明此步無解
? ? }
? ? //判斷下一步是否能走，下一步有8中情況0-7，傳入當(dāng)前步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;
? ? }
}