java學(xué)習(xí)筆記之馬踏棋盤算法
馬踏棋盤或騎士周游問題
1、馬踏棋盤算法也被稱為騎士周游問題
2、將馬隨機(jī)放在國際象棋的 8×8 棋盤 Board[0～7][0～7]的某個(gè)方格中，馬按走棋規(guī)則(馬走日字)進(jìn)行移動(dòng)。要求每個(gè)方格只進(jìn)入一次，走遍棋盤上全部 64 個(gè)方格
思路
會(huì)使用到深度優(yōu)先思想和類似迷宮問題的尋路策略問題，和八皇后問題也有相似。
1、用一個(gè)二維數(shù)組建立整張棋盤。用另外一個(gè)二維數(shù)組保存棋盤的每一個(gè)位置是否走過
2、馬在棋盤上有一個(gè)初始位置，將這個(gè)位置設(shè)為已走過，并將步數(shù)設(shè)為1.
3、獲得在這個(gè)位置上，馬下一步能走的位置集合。
4、遍歷集合里的所有位置，如果那個(gè)位置沒走過，下一步（步數(shù)+1）就走它（遞歸）
5、設(shè)置遞歸結(jié)束的標(biāo)志.用一個(gè)布爾變量標(biāo)志游戲是否成功。當(dāng)游戲成功時(shí)，步數(shù)應(yīng)該等于棋盤格子數(shù)。假如某一次，馬走完了所有能走的下一步位置，步數(shù)還小于棋盤格子數(shù)并且還沒成功，說明這個(gè)位置不能成功的完成游戲，就把這個(gè)位置恢復(fù)原樣（棋盤設(shè)為0，設(shè)為未走過），接下來的遞歸會(huì)重新去尋找合適的路。如果步數(shù)等于棋盤總格子數(shù)，說明游戲成功，把標(biāo)志的布爾變量設(shè)為true，這樣在層層返回時(shí)就不會(huì)再進(jìn)入上面的條件，遞歸就會(huì)逐漸結(jié)束而不會(huì)深入下去。
涉及到的方法：
根據(jù)此時(shí)的位置，判斷馬接下來能走的位置集合。
x的值代表列而y的值代表行
馬是按照日字走的，所有當(dāng)它在中間時(shí)最多有8種位置可以走，一 一判斷那個(gè)位置是否超過棋盤邊界。
每種可能都是if，而不是if-else if，因?yàn)橐@得所有的可能性，而不是找出一個(gè)
假如list時(shí)一定要新建一個(gè)坐標(biāo)，不能使用同一個(gè)，不然值就會(huì)互相影響
/**
? ? ?* 根據(jù)現(xiàn)在的坐標(biāo)返回可以走的坐標(biāo) x列y行
? ? ?*
? ? ?* @param current
? ? ?* @return
? ? ?*/
? ? public static ArrayList<Point> findWay(Point current) {
? ? ? ? ArrayList<Point> res = new ArrayList<>();
? ? ? ? //可以走的坐標(biāo)
? ? ? ? Point p = new Point();
? ? ? ? //5
? ? ? ? if ((p.x = current.x - 2) >= 0 && (p.y = current.y - 1) >= 0) {
? ? ? ? ? ? res.add(new Point(p));
? ? ? ? }
? ? ? ? //6
? ? ? ? if ((p.x = current.x - 1) >= 0 && (p.y = current.y - 2) >= 0) {
? ? ? ? ? ? res.add(new Point(p));
? ? ? ? }
? ? ? ? //7
? ? ? ? if ((p.x = current.x + 1) < X && (p.y = current.y - 2) >= 0) {
? ? ? ? ? ? res.add(new Point(p));
? ? ? ? }
? ? ? ? //0
? ? ? ? if ((p.x = current.x + 2) < X && (p.y = current.y - 1) >= 0) {
? ? ? ? ? ? res.add(new Point(p));
? ? ? ? }
? ? ? ? //1
? ? ? ? if ((p.x = current.x + 2) < X && (p.y = current.y + 1) < Y) {
? ? ? ? ? ? res.add(new Point(p));
? ? ? ? }
? ? ? ? //2
? ? ? ? if ((p.x = current.x + 1) < X && (p.y = current.y + 2) < Y) {
? ? ? ? ? ? res.add(new Point(p));
? ? ? ? }
? ? ? ? //3
? ? ? ? if ((p.x = current.x - 1) >= 0 && (p.y = current.y + 2) < Y) {
? ? ? ? ? ? res.add(new Point(p));
? ? ? ? }
? ? ? ? //4
? ? ? ? if ((p.x = current.x - 2) >= 0 && (p.y = current.y + 1) < Y) {
? ? ? ? ? ? res.add(new Point(p));
? ? ? ? }
? ? ? ? return res;
? ? }馬塔棋盤
不能單純以step < X * Y來判斷是否完成游戲，因?yàn)檫f歸回溯時(shí)步數(shù)也會(huì)回溯，所以要設(shè)置一個(gè)變量
?/**
? ? ?* 馬踏棋盤算法
? ? ?*
? ? ?* @param chess 棋盤
? ? ?* @param row ? 坐標(biāo)行
? ? ?* @param col ? 坐標(biāo)列
? ? ?* @param step ?步數(shù)
? ? ?*/
? ? public static void traversalChessboard(int[][] chess, int row, int col, int step) {
? ? ? ? //先走一步
? ? ? ? chess[row][col] = step;
? ? ? ? visit[row][col] = true;
? ? ? ? //下一步能走的地
? ? ? ? ArrayList<Point> way = findWay(new Point(col, row));
? ? ? ? while (!way.isEmpty()) {
? ? ? ? ? ? //取出一個(gè)能走的地方
? ? ? ? ? ? Point point = way.remove(0);
? ? ? ? ? ? //走下一步
? ? ? ? ? ? if (!visit[point.y][point.x]) {
? ? ? ? ? ? ? ? traversalChessboard(chess, point.y, point.x, step + 1);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? //判斷是否完成游戲，如果沒完成就要回溯
? ? ? ? if (step < X * Y && !finshed) {
? ? ? ? ? ? chess[row][col] = 0;
? ? ? ? ? ? visit[row][col] = false;
? ? ? ? }else {
? ? ? ? ? ? finshed=true;
? ? ? ? }
? ? }優(yōu)化
這樣計(jì)算效率比較低，算法比較慢。實(shí)際上當(dāng)我們獲得下一步可以走的位置數(shù)組時(shí)是按照固定的56701234順序排列的，但是這樣效率不高，我們?cè)诳紤]到走下一步時(shí)，應(yīng)該先走對(duì)應(yīng)下一步的可能性最少的那一步，比如如果7的下一步有3種可能，而5的下一步有6種可能，那先7后5的效率會(huì)更高。
所以我們可以使用貪心算法對(duì)獲得的這個(gè)步數(shù)集合根據(jù)他們下一步的可能性進(jìn)行由小到大的排序。
/**
? ? ?* 貪心算法優(yōu)化
? ? ?* @param ps
? ? ?*/
? ? public static void sort(ArrayList<Point> ps){
? ? ? ? ps.sort(new Comparator<Point>() {
? ? ? ? ? ? @Override
? ? ? ? ? ? public int compare(Point o1, Point o2) {
? ? ? ? ? ? ? ? int way1 = findWay(o1).size();
? ? ? ? ? ? ? ? int way2 = findWay(o2).size();
? ? ? ? ? ? ? ? if(way1<way2){
? ? ? ? ? ? ? ? ? ? return -1;
? ? ? ? ? ? ? ? }else if(way1==way2){
? ? ? ? ? ? ? ? ? ? return 0;
? ? ? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? ? ? return 1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? });
}對(duì)Comparetor.compare(o1, o2)方法的返回值，如果返回的值小于零，則不交換兩個(gè)o1和o2的位置；如果返回的值大于零，則交換o1和o2的位置。 注意，不論在compare(o1, o2)中是如何實(shí)現(xiàn)的（第一種實(shí)現(xiàn)方式是 o1-02, 第二種實(shí)現(xiàn)方式是 o2 - o1），都遵循上述原則，即返回值小于零，則交換o1和o2的位置；返回值大于零，則不交換o1和o2的位置。 所以，如果采用第一種實(shí)現(xiàn)方式，即 o1 - o2, 那么將是升序排序。因?yàn)樵谠寂判蛑衞1在o2的前邊，如果o1小于o2，那么o1 - o2小于零，即返回值是小于零，但是小于零是不會(huì)交換o1和o2的位置的，所以o1依然排在o2的前邊，是升序；如果o1大于o2，那么o1 - o2大于零，即返回值是大于零，大于零是要交換o1和o2的位置的，所以要改變?cè)寂判蛑衞1和o2的位置，那么依然是升序
最終代碼
package algorithm;
import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
/**
?* 馬踏棋盤算法
?*/
public class HorseChessboard {
? ? static int X;//列
? ? static int Y;//行
? ? static boolean[][] visit;
? ? static boolean finshed;
? ? public static void main(String[] args) {
? ? ? ? X = 8;
? ? ? ? Y = 8;
? ? ? ? visit = new boolean[X][Y];
? ? ? ? finshed = false;
? ? ? ? int[][] chess = new int[X][Y];
? ? ? ? long s = System.currentTimeMillis();
? ? ? ? traversalChessboard(chess, 2, 0, 1);
? ? ? ? long e=System.currentTimeMillis();
? ? ? ? System.out.println(e-s);
? ? ? ? for (int i = 0; i < chess.length; i++) {
? ? ? ? ? ? System.out.println(Arrays.toString(chess[i]));
? ? ? ? }
? ? }
? ? /**
? ? ?* 馬踏棋盤算法
? ? ?*
? ? ?* @param chess 棋盤
? ? ?* @param row ? 坐標(biāo)行
? ? ?* @param col ? 坐標(biāo)列
? ? ?* @param step ?步數(shù)
? ? ?*/
? ? public static void traversalChessboard(int[][] chess, int row, int col, int step) {
? ? ? ? //先走一步
? ? ? ? chess[row][col] = step;
? ? ? ? visit[row][col] = true;
? ? ? ? //下一步能走的地
? ? ? ? ArrayList<Point> way = findWay(new Point(col, row));
? ? ? ? sort(way);
? ? ? ? while (!way.isEmpty()) {
? ? ? ? ? ? //取出一個(gè)能走的地方
? ? ? ? ? ? Point point = way.remove(0);
? ? ? ? ? ? //走下一步
? ? ? ? ? ? if (!visit[point.y][point.x]) {
? ? ? ? ? ? ? ? traversalChessboard(chess, point.y, point.x, step + 1);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if (step < X * Y && !finshed) {
? ? ? ? ? ? chess[row][col] = 0;
? ? ? ? ? ? visit[row][col] = false;
? ? ? ? }else {
? ? ? ? ? ? finshed=true;
? ? ? ? }
? ? }
? ? /**
? ? ?* 根據(jù)現(xiàn)在的坐標(biāo)返回可以走的坐標(biāo) x列y行
? ? ?*
? ? ?* @param current
? ? ?* @return
? ? ?*/
? ? public static ArrayList<Point> findWay(Point current) {
? ? ? ? ArrayList<Point> res = new ArrayList<>();
? ? ? ? //可以走的坐標(biāo)
? ? ? ? Point p = new Point();
? ? ? ? //5
? ? ? ? if ((p.x = current.x - 2) >= 0 && (p.y = current.y - 1) >= 0) {
? ? ? ? ? ? res.add(new Point(p));
? ? ? ? }
? ? ? ? //6
? ? ? ? if ((p.x = current.x - 1) >= 0 && (p.y = current.y - 2) >= 0) {
? ? ? ? ? ? res.add(new Point(p));
? ? ? ? }
? ? ? ? //7
? ? ? ? if ((p.x = current.x + 1) < X && (p.y = current.y - 2) >= 0) {
? ? ? ? ? ? res.add(new Point(p));
? ? ? ? }
? ? ? ? //0
? ? ? ? if ((p.x = current.x + 2) < X && (p.y = current.y - 1) >= 0) {
? ? ? ? ? ? res.add(new Point(p));
? ? ? ? }
? ? ? ? //1
? ? ? ? if ((p.x = current.x + 2) < X && (p.y = current.y + 1) < Y) {
? ? ? ? ? ? res.add(new Point(p));
? ? ? ? }
? ? ? ? //2
? ? ? ? if ((p.x = current.x + 1) < X && (p.y = current.y + 2) < Y) {
? ? ? ? ? ? res.add(new Point(p));
? ? ? ? }
? ? ? ? //3
? ? ? ? if ((p.x = current.x - 1) >= 0 && (p.y = current.y + 2) < Y) {
? ? ? ? ? ? res.add(new Point(p));
? ? ? ? }
? ? ? ? //4
? ? ? ? if ((p.x = current.x - 2) >= 0 && (p.y = current.y + 1) < Y) {
? ? ? ? ? ? res.add(new Point(p));
? ? ? ? }
? ? ? ? return res;
? ? }
? ? /**
? ? ?* 貪心算法優(yōu)化
? ? ?* @param ps
? ? ?*/
? ? public static void sort(ArrayList<Point> ps){
? ? ? ? ps.sort(new Comparator<Point>() {
? ? ? ? ? ? @Override
? ? ? ? ? ? public int compare(Point o1, Point o2) {
? ? ? ? ? ? ? ? int way1 = findWay(o1).size();
? ? ? ? ? ? ? ? int way2 = findWay(o2).size();
? ? ? ? ? ? ? ? if(way1<way2){
? ? ? ? ? ? ? ? ? ? return -1;
? ? ? ? ? ? ? ? }else if(way1==way2){
? ? ? ? ? ? ? ? ? ? return 0;
? ? ? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? ? ? return 1;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? });
? ? }
}以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
Java中實(shí)現(xiàn)將jar包內(nèi)文件資源釋放出來
這篇文章主要介紹了Java中實(shí)現(xiàn)將jar包內(nèi)文件資源釋放出來的方法，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-08-08
這篇文章主要介紹了不了解這12個(gè)語法糖，別說你會(huì)Java，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-08-08
Springboot使用pdfbox提取PDF圖片的代碼示例
PDFBox是一個(gè)用于創(chuàng)建和處理PDF文檔的Java庫，它可以使用Java代碼創(chuàng)建、讀取、修改和提取PDF文檔中的內(nèi)容，本文就給大家介紹Springboot如何使用pdfbox提取PDF圖片，感興趣的同學(xué)可以借鑒參考2023-06-06
這篇文章主要介紹了java設(shè)計(jì)模式之六大原則，對(duì)設(shè)計(jì)模式感興趣的同學(xué)，可以參考下2021-05-05
Java創(chuàng)建,編輯與刪除Excel迷你圖表的實(shí)現(xiàn)方法
迷你圖是Excel工作表單元格中表示數(shù)據(jù)的微型圖表。本文將通過Java代碼示例介紹如何在Excel中創(chuàng)建迷你圖表，以及編輯和刪除表格中的迷你圖表，需要的可以參考一下2022-05-05
MyBatis-Plus攔截器對(duì)敏感數(shù)據(jù)實(shí)現(xiàn)加密
做課程項(xiàng)目petstore時(shí)遇到需要加密屬性的問題，而MyBatis-Plus為開發(fā)者提供了攔截器的相關(guān)接口，本文主要介紹通過MyBatis-Plus的攔截器接口自定義一個(gè)攔截器類實(shí)現(xiàn)敏感數(shù)據(jù)如用戶密碼的加密功能，感興趣的可以了解一下2021-11-11
Spring?Boot2.6.0新特性之默認(rèn)禁止循環(huán)引用
Spring?Boot2.6.0為我們帶來很多好用的新特性/改進(jìn),這篇文章主要給大家介紹了關(guān)于Spring?Boot2.6.0新特性之默認(rèn)禁止循環(huán)引用的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-02-02
這篇文章主要介紹了詳解Java編程中線程的掛起、恢復(fù)和終止的方法,線程是Java學(xué)習(xí)中的重點(diǎn)和難點(diǎn)知識(shí),需要的朋友可以參考下2015-09-09
在java poi導(dǎo)入Excel通用工具類示例詳解
這篇文章主要給大家介紹了關(guān)于在java poi導(dǎo)入Excel通用工具類的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2017-09-09
這篇文章主要介紹了Maven中央倉庫地址配置大全，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-06-06