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

This article introduces the relevant knowledge of "how to achieve horse chessboard algorithm in java". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

The problem of horse stepping on the chessboard or knight traveling around

1. The horse pedal chessboard algorithm is also known as the knight travel problem.

2. Put the horse randomly in a box of 8 × 8 chess board Board [0x7] [0x7], and the horse moves according to the rules of chess (horse walking Japanese word). Each square is required to enter only once and walk through all 64 squares on the chessboard.

Train of thought

It uses depth-first thinking and pathfinding strategies like maze problems, which are similar to the eight queens problem.

1. Create the whole chessboard with a two-dimensional array. Use another two-dimensional array to save whether each position of the chessboard has passed.

2. The horse has an initial position on the chessboard, set this position to have passed, and set the number of steps to 1.

3. Get the position where the horse can take the next step in this position.

4. Traverse all the positions in the collection, and if that position is not passed, the next step (number of steps + 1) is to take it (recursion)

5. Set the flag for the end of recursion. Use a Boolean variable to mark the success of the game. When the game is successful, the number of steps should be equal to the number of checkerboards. If at one time, the horse has finished all the next steps that can be taken, the number of steps is less than the number of checkerboards and has not been successful, which means that this position cannot successfully complete the game, the position will be restored to its original position (the chessboard is set to 0, set to not gone through), and the next recursion will re-find the right way. If the number of steps is equal to the total grid number of the chessboard, the game is successful. Set the Boolean variable of the flag to true, so that when you return layer by layer, you will not enter the above conditions, and the recursion will gradually end and will not go further.

The methods involved:

According to the position at this time, judge the position set where the horse can go next.

The value of x represents the column and the value of y represents the row

The horse follows the Japanese character, so when it is in the middle, there are up to eight positions to determine whether that position exceeds the boundary of the chessboard.

Every possibility is if, not if-else if, because you want to get all the possibilities, not to find one.

If you must create a new coordinate when list, do not use the same coordinate, otherwise the values will affect each other.

/ * return the walkable coordinates according to the current coordinates x column y row * * @ param current * @ return * / public static ArrayList findWay (Point current) {ArrayList res = new ArrayList (); / / walkable coordinates 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 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 ps){ ps.sort(new Comparator() { @Override public int compare(Point o1, Point o2) { int way1 = findWay(o1).size(); int way2 = findWay(o2).size(); if(way1= 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 } / * greedy algorithm optimization * @ param ps * / public static void sort (ArrayList ps) {ps.sort (new Comparator () {@ Override public int compare (Point o1, Point O2) {int way1 = findWay (o1). Size (); int way2 = findWay (O2). Size (); if (way1)

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.