Shulou(Shulou.com)06/01 Report--

This article will explain in detail how to use java to achieve horse stepping board, Xiaobian thinks it is quite practical, so share it for everyone to make a reference, I hope you can gain something after reading this article.

specific contents are as follows

The horse treading board algorithm is also known as the knight's tour problem

The horse is randomly placed in a certain square of the 8x8 chessboard of expired chess. The horse moves according to the rules of chess. Each square is required to enter only once, and all 64 squares on the chessboard are traveled.

Knight Tour Question Ending Steps and Ideas

1. Create a chessBoard, which is a two-dimensional array

2. Set the current position to already visited, and then calculate the positions that the horse can still walk according to the current position, and put them into an ArrayList, up to 8 positions.

3. ArrayList variable stored in all positions, see which can be passed through

4. Determine if the horse has completed the knight's tour problem

Note: Different horse walks will result in different results, and efficiency will also have an impact.

code implementation

public class HorseChessBoard { private static int X; //Number of columns on the board private static int Y; //Number of rows on the board //Create an array to mark whether each position on the chessboard has been visited private static boolean[] visited; //Use an attribute to mark whether all positions on the board have been visited, i.e. whether it succeeded private static boolean finish; //if true means success public static void main(String[] args) { X = 8; Y = 8; int row = 1; int col = 1; int[][] chessboard = new int[X][Y]; visited = new boolean[X * Y]; long start = System.currentTimeMillis(); traversalChessboard(chessboard, row-1, col-1, 1); long end = System.currentTimeMillis(); System.out.println(end - start); for (int[] rows : chessboard) { for (int step : rows) { System.out.print(step + " "); } System.out.println(); } } //actually travel around the problem public static void traversalChessboard(int[][] chessboard, int row, int col, int step) { if (finish) return; chessboard[row][col] = step; visited[row * X + col] = true; //marks that the location has been visited //Get the next location that the current location can go to List ps = next(new Point(col, row)); sort(ps); //Traverse ps while (! ps.isEmpty()) { Point p = ps.remove(0); //remove the next available position //determine whether the point has been visited if (! visited[p.y * X + p.x]) { traversalChessboard(chessboard, p.y, p.x, step+1); } } //1. The board has not finished moving to its current position. //2. The board is in a backtracking process. if (step

< X * Y && !finish) { chessboard[row][col] = 0; visited[row * X + col] = false; } else { finish = true; } } //根据当前这一步的所有的下一步的选择位置进行非递减排序 public static void sort(List ps) { ps.sort(new Comparator() { @Override public int compare(Point o1, Point o2) { //获取o1,o2下一步所有个数 int count1 = next(o1).size(); int count2 = next(o2).size(); if (count1 < count2) { return -1; } else if (count1 == count2) { return 0; } else { return 1; } } }); } //Point:根据当前位置(point对象) //根据当前位置，计算马儿还能走那些位置，并放到一个集合中(ArrayList)，最多8个位置 public static List next(Point curPoint) { //创建list集合 List ps = new ArrayList(); //创建一个point Point p1 = new Point(); if ((p1.x = curPoint.x-2) >

= 0 && (p1.y = curPoint.y-1) >= 0) { ps.add(new Point(p1)); } if ((p1.x = curPoint.x-1) >= 0 && (p1.y = curPoint.y-2) >= 0) { ps.add(new Point(p1)); } if ((p1.x = curPoint.x+1)

< X && (p1.y = curPoint.y-2) >

= 0) { ps.add(new Point(p1)); } if ((p1.x = curPoint.x+2)

< X && (p1.y = curPoint.y-1) >

= 0) { ps.add(new Point(p1)); } if ((p1.x = curPoint.x+2)

< X && (p1.y = curPoint.y+1) < Y) { ps.add(new Point(p1)); } if ((p1.x = curPoint.x+1) < X && (p1.y = curPoint.y+2) < Y) { ps.add(new Point(p1)); } if ((p1.x = curPoint.x-1) >

= 0 && (p1.y = curPoint.y+2)

< Y) { ps.add(new Point(p1)); } if ((p1.x = curPoint.x-2) >

= 0 && (p1.y = curPoint.y+1) < Y) { ps.add(new Point(p1)); } return ps; }} About "how to use java to achieve horse pedal board" This article is shared here, I hope the above content can be of some help to everyone, so that you can learn more knowledge, if you think the article is good, please share it to let more people see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.