java學習筆記之馬踏棋盤算法
馬踏棋盤或騎士周遊問題
1、馬踏棋盤算法也被稱為騎士周遊問題
2、將馬隨機放在國際象棋的 8×8 棋盤 Board[0～7][0～7]的某個方格中，馬按走棋規則(馬走日字)進行移動。要求每個方格隻進入一次，走遍棋盤上全部 64 個方格
思路
會使用到深度優先思想和類似迷宮問題的尋路策略問題，和八皇後問題也有相似。
1、用一個二維數組建立整張棋盤。用另外一個二維數組保存棋盤的每一個位置是否走過
2、馬在棋盤上有一個初始位置，將這個位置設為已走過，並將步數設為1.
3、獲得在這個位置上，馬下一步能走的位置集合。
4、遍歷集合裡的所有位置，如果那個位置沒走過，下一步（步數+1）就走它（遞歸）
5、設置遞歸結束的標志.用一個佈爾變量標志遊戲是否成功。當遊戲成功時，步數應該等於棋盤格子數。假如某一次，馬走完瞭所有能走的下一步位置，步數還小於棋盤格子數並且還沒成功，說明這個位置不能成功的完成遊戲，就把這個位置恢復原樣（棋盤設為0，設為未走過），接下來的遞歸會重新去尋找合適的路。如果步數等於棋盤總格子數，說明遊戲成功，把標志的佈爾變量設為true，這樣在層層返回時就不會再進入上面的條件，遞歸就會逐漸結束而不會深入下去。
涉及到的方法：
根據此時的位置，判斷馬接下來能走的位置集合。
x的值代表列而y的值代表行
馬是按照日字走的，所有當它在中間時最多有8種位置可以走，一 一判斷那個位置是否超過棋盤邊界。
每種可能都是if，而不是if-else if，因為要獲得所有的可能性，而不是找出一個
假如list時一定要新建一個坐標，不能使用同一個，不然值就會互相影響
/**
* 根據現在的坐標返回可以走的坐標 x列y行
*
* @param current
* @return
*/
public static ArrayList<Point> findWay(Point current) {
ArrayList<Point> res = new ArrayList<>();
//可以走的坐標
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來判斷是否完成遊戲，因為遞歸回溯時步數也會回溯，所以要設置一個變量
/**
* 馬踏棋盤算法
*
* @param chess 棋盤
* @param row 坐標行
* @param col 坐標列
* @param step 步數
*/
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()) {
//取出一個能走的地方
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;
}
}
優化
這樣計算效率比較低，算法比較慢。實際上當我們獲得下一步可以走的位置數組時是按照固定的56701234順序排列的，但是這樣效率不高，我們在考慮到走下一步時，應該先走對應下一步的可能性最少的那一步，比如如果7的下一步有3種可能，而5的下一步有6種可能，那先7後5的效率會更高。
所以我們可以使用貪心算法對獲得的這個步數集合根據他們下一步的可能性進行由小到大的排序。
/**
* 貪心算法優化
* @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;
}
}
});
}
對Comparetor.compare(o1, o2)方法的返回值，如果返回的值小於零，則不交換兩個o1和o2的位置；如果返回的值大於零，則交換o1和o2的位置。 註意，不論在compare(o1, o2)中是如何實現的（第一種實現方式是 o1-02, 第二種實現方式是 o2 – o1），都遵循上述原則，即返回值小於零，則交換o1和o2的位置；返回值大於零，則不交換o1和o2的位置。 所以，如果采用第一種實現方式，即 o1 – o2, 那麼將是升序排序。因為在原始排序中o1在o2的前邊，如果o1小於o2，那麼o1 – o2小於零，即返回值是小於零，但是小於零是不會交換o1和o2的位置的，所以o1依然排在o2的前邊，是升序；如果o1大於o2，那麼o1 – o2大於零，即返回值是大於零，大於零是要交換o1和o2的位置的，所以要改變原始排序中o1和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 坐標行
* @param col 坐標列
* @param step 步數
*/
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()) {
//取出一個能走的地方
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;
}
}
/**
* 根據現在的坐標返回可以走的坐標 x列y行
*
* @param current
* @return
*/
public static ArrayList<Point> findWay(Point current) {
ArrayList<Point> res = new ArrayList<>();
//可以走的坐標
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;
}
/**
* 貪心算法優化
* @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;
}
}
});
}
}
以上就是本文的全部內容，希望對大傢的學習有所幫助，也希望大傢多多支持WalkonNet。
推薦閱讀：
- java實現馬踏棋盤的算法
- java數據結構與算法之馬踏棋盤
- java實現馬踏棋盤遊戲
- Java List的sort()方法改寫compare()實現升序,降序,倒序的案例
- java中ArrayList的兩種排序方法實例