马踏棋盘算法介绍和游戏演示
马踏棋盘算法也被称为骑士周游问题将马随机放在国际象棋的8×8棋盘Board[0～7][0～7]的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格骑士周游问题的解决思路
创建棋盘chessBoard,是一个二维数组
将当前位置设置为已经访问,然后根据当前位置,计算马儿还能走哪些位置,并放入到一个集合中(arrayList),最多有8个位置,每走一步,就是用step+1
遍历arrayList中存放的所有位置看看哪个可以走通,如果走通就继续,走不通就回溯
判断马儿是否完成了任务,使用step和应该走的步数比较,如果没有达到数量,则表示没有完成任务,将整个棋盘置为0.
注意:马儿不同的走法,会得到不同的结果,效率也会有影响(优化)
package com.qiu.house; import com.sun.org.apache.regexp.internal.RE; import java.awt.*; import java.util.ArrayList; public class HorseChessboard { //棋盘的列数 private static int X; //棋盘的行数 private static int Y; //创建一个数组,标记棋盘的各个位置是否被访问过 private static boolean visited[]; //使用一个属性,标记是否棋盘的所有位置都被访问过 private static boolean finished; public static void main(String[] args) { System.out.println("骑士周游算法,开始运行!"); //测试骑士周游算法是否正确 X = 8; Y = 8; //马儿初始位置的行,从1开始 int row = 1; int column = 1; //创建棋盘 int[][] chessboard = new int[X][Y]; //初始值都是false visited = new boolean[X * Y]; //测试一下耗时 long start = System.currentTimeMillis(); traversalChessboard(chessboard, row - 1, column - 1, 1); long end = System.currentTimeMillis(); System.out.println("共耗时:" + (end - start) + "毫秒"); //输出棋盘的最后情况 for (int[] rows : chessboard) { for (int step : rows) { System.out.print(step + "\t"); } System.out.println(); } } /** * 完成骑士周游算法 * * @param chessboard 棋盘 * @param row 马儿当前的位置的行从0开始 * @param column 马儿当前的位置的列,从0开始 * @param step 是第几步,初始位置就是第一步 */ public static void traversalChessboard(int[][] chessboard, int row, int column, int step) { chessboard[row][column] = step; //[]里面表示马儿的初始位置 visited[row * X + column] = true; //获取当前位置,可以走的下一个位置的集合 ArrayList<Point> ps = next(new Point(column, row)); //开始遍历ArrayList所有的位置 while (!ps.isEmpty()) { Point p = ps.remove(0); //判断该点是否已经访问过 if (!visited[p.y * X + p.x]) { //说明没有访问过 traversalChessboard(chessboard, p.y, p.x, step + 1); } } //判断马儿是否完成了任务,使用step和应该走的步数比较,如果没有达到数量,则表示没有完成任务,将整个棋盘置为0. //下面的step<x*y是有两种情况 1. 棋盘到目前位置,仍然没有走完 2.棋盘处于一个回溯过程 if (step < X * Y && !finished) { chessboard[row][column] = 0; visited[row * X + column] = false; } else { finished = true; } } /** * 将当前位置设置为已经访问,然后根据当前位置,计算马儿还能走哪些位置,并放入到一个集合中(arrayList),最多有8个位置,每走一步,就是用step+1 * * @param curPoint 当前的位置 * @return */ public static ArrayList<Point> next(Point curPoint) { //创建一个ArrayList ArrayList<Point> ps = new ArrayList<Point>(); //创建一个Point Point p1 = new Point(); //表示马儿可以走5这个位置 if((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y -1) >= 0) { ps.add(new Point(p1)); } //判断马儿可以走6这个位置 if((p1.x = curPoint.x - 1) >=0 && (p1.y=curPoint.y-2)>=0) { ps.add(new Point(p1)); } //判断马儿可以走7这个位置 if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) { ps.add(new Point(p1)); } //判断马儿可以走0这个位置 if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) { ps.add(new Point(p1)); } //判断马儿可以走1这个位置 if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) { ps.add(new Point(p1)); } //判断马儿可以走2这个位置 if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) { ps.add(new Point(p1)); } //判断马儿可以走3这个位置 if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) { ps.add(new Point(p1)); } //判断马儿可以走4这个位置 if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) { ps.add(new Point(p1)); } return ps; } }需要39秒才能完成全部,接下来进行策略优化:
使用贪心算法进行优化:
我们获取当前位置,可以租的下一个位置的集合//获取当前位置可以走的下一个位置的集合 ArrayList<Point> = ps next(new point(column,row))我们需要对ps中所有的point的下一步的所有集合的数目,进行非递减排序就ok优化:
//根据当前这个一步的所有的下一步的选择位置，进行非递减排序, 减少回溯的次数 public static void sort(ArrayList<Point> ps) { ps.sort(new Comparator<Point>() { @Override public int compare(Point o1, Point o2) { // TODO Auto-generated method stub //获取到o1的下一步的所有位置个数 int count1 = next(o1).size(); //获取到o2的下一步的所有位置个数 int count2 = next(o2).size(); if (count1 < count2) { return -1; } else if (count1 == count2) { return 0; } else { return 1; } } }); }优化后的运行显示:
