基于Java實現(xiàn)馬踏棋盤游戲算法

更新時間：2022年02月14日 17:03:08 作者：L_Mcode

這篇文章主要為大家詳細介紹了基于Java實現(xiàn)馬踏棋盤游戲算法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

馬踏棋盤很好實現(xiàn)，但有時運行起來特別慢，還可能出不來結果，最常用的就是深度優(yōu)先遍歷+回溯，相信大家都學過數(shù)據(jù)結構，對圖的深度遍歷都有了解，下面就是代碼的實現(xiàn)，如果對代碼理解有困難，可以先熟悉一下圖的深度優(yōu)先遍歷

大家可以把棋盤改小一些測試，8x8的確實很慢

import java.util.Arrays;

/**
?* 騎士周游問題
?* @author LM_Code
?* @create 2019-03-17-18:57
?*/
public class KnightProblem {
? ? static final int SIZE = 8;//設置棋盤的行數(shù)和列數(shù)>=5時才有解
? ? static final int[][] A = new int[SIZE][SIZE];//初始化棋盤，數(shù)組中所有值默認為0
? ? static final int[] NEXT= new int[]{1, 2};//設置馬的下一步，用空間為2的數(shù)組代替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)){//如果可以走，繼續(xù)遞歸
? ? ? ? ? ? ? ? //判斷此時的下一步，是否能走完棋盤
? ? ? ? ? ? ? ? if(method(NEXT, tag+1)){//能，返回true，遞歸結束
? ? ? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? //此時的下一步不能走完棋盤，則繼續(xù)尋找第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;
? ? }
}

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章:

淺談一下Java中的ReentrantLock
這篇文章主要介紹了淺談一下Java中的ReentrantLock,這個類是JUC工具包中對線程安全問題提供的一種解決方案,它主要是用來給對象上鎖,保證同一時間這能有一個線程在訪問當前對象,需要的朋友可以參考下
2023-09-09
Java通過HttpClient進行HTTP請求的代碼詳解
Apache?HttpClient是一個功能強大且廣泛使用的Java庫，它提供了方便的方法來執(zhí)行HTTP請求并處理響應。本文將介紹如何使用HttpClient庫進行HTTP請求，包括GET請求、POST請求、添加參數(shù)和請求體、設置請求頭等操作,需要的朋友可以參考下
2023-05-05
SpringBoot集成Redisson實現(xiàn)消息隊列的示例代碼
本文介紹了如何在SpringBoot中通過集成Redisson來實現(xiàn)消息隊列的功能,包括RedisQueue、RedisQueueInit、RedisQueueListener、RedisQueueService等相關組件的實現(xiàn)和測試,感興趣的可以了解一下
2024-10-10
使用Spring Security集成手機驗證碼登錄功能實現(xiàn)
本文詳細介紹了如何利用SpringSecurity來實現(xiàn)手機驗證碼的注冊和登錄功能,在登錄過程中,同樣需通過驗證碼進行驗證,文章還提供了相關的代碼實現(xiàn)
2024-10-10
Java實現(xiàn)文件分割與合并
這篇文章主要介紹了Java實現(xiàn)文件分割與合并，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2020-05-05
Spring?boot配置綁定和配置屬性校驗的方式詳解
這篇文章主要介紹了Spring?boot配置綁定和配置屬性校驗,SpringBoot 提供了2 種方式進行配置綁定，即使用 @ConfigurationProperties 注解和使用 @Value 注解，需要的朋友可以參考下
2022-05-05
分布式消息隊列RocketMQ概念詳解
RocketMQ?是阿里開源的分布式消息中間件，跟其它中間件相比，RocketMQ?的特點是純JAVA實現(xiàn)，是一套提供了消息生產，存儲，消費全過程API的軟件系統(tǒng)，本文詳細介紹了分布式消息隊列RocketMQ概念，需要的朋友可以參考下
2023-05-05
在Spring Boot中如何使用Cookies詳析
這篇文章主要給大家介紹了關于在Spring Boot中如何使用Cookies的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者使用Spring Boot具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧
2019-11-11
java設計模式之建造者模式學習
建造者模式(Builder Pattern)主要用于“分步驟構建一個復雜的對象”，在這其中“分步驟”是一個穩(wěn)定的算法，下面給出了詳細的示例
2014-01-01
通過實例解析spring環(huán)繞通知原理及用法
這篇文章主要介紹了通過實例解析spring環(huán)繞通知原理及用法,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2020-10-10