1. Introduction of horse board algorithm and game demonstration
-
The horse-step checkerboard algorithm is also known as the knight’s tour problem
-
The horse is randomly placed on a square of Board[0 ~ 7][0 ~ 7] of 8×8 chess, and the horse moves according to the rules of chess (horse moves day character). Each square is required to enter only once, covering all 64 squares on the board
-
Game demo: www.4399.com/flash/14626…
2. Code implementation of horse board game
-
The checkerboard problem is actually an application of depth-first search (DFS) of graphs.
-
- If you use backtracking (depth-first search) to solve this problem, if the horse steps on 53 points, as shown in the picture: it reaches the 53rd coordinate (1,0), and finds that it has reached the end, it has no choice but to back up, look at other paths, and keep backtracking on the board… .
-
The problem of the first method is analyzed, and the greedyalgorithm is used for optimization. Solve the chessboard problem.
- Use the previous game to verify that the algorithm is correct.
public class HorseChessboard {
/** * the number of columns */
private static int X;
/** * the number of lines on the board */
private static int Y;
/** * creates an array to mark whether the various positions of the board have been accessed */
private static boolean visited[];
/** * uses an attribute that marks whether all positions of the board are accessed * if true, success */
private static boolean finished;
public static void main(String[] args) {
System.out.println("Knight Tour algorithm, running ~~");
// Test whether the knight tour algorithm is correct
X = 8;
Y = 8;
// The line of the horse's initial position, numbered from 1
int row = 1;
// The column of the horse's initial position, numbered from 1
int column = 1;
// Create the checkerboard
int[][] chessboard = new int[X][Y];
// The initial value is false
visited = new boolean[X * Y];
// Test the elapsed time
long start = System.currentTimeMillis();
traversalChessboard(chessboard, row - 1, column - 1.1);
long end = System.currentTimeMillis();
System.out.println("Total time:" + (end - start) + "Ms");
// Outputs the final condition of the checkerboard
for (int[] rows : chessboard) {
for (int step : rows) {
System.out.print(step + "\t"); } System.out.println(); }}/** * The algorithm to complete the knight tour problem **@paramChessboard board *@paramRow the current position of the horse starts at 0 *@paramColumn The column of the horse's current position starts at 0 *@paramStep is the number of steps, the initial position is step 1 */
public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
chessboard[row][column] = step;
//row = 4 X = 8 column = 4 = 4 * 8 + 4 = 36
visited[row * X + column] = true; // Mark that the location has been accessed
// Get the collection of the next positions that the current position can go to
ArrayList<Point> ps = next(new Point(column, row));
// Undecrement the number of next positions of all points in photoshop
sort(ps);
/ / traverse the ps
while(! ps.isEmpty()) {// Select the next available position
Point p = ps.remove(0);
// Determine whether the point has already been accessed
if(! visited[p.y * X + p.x]) {// Indicates that it has not been accessed
traversalChessboard(chessboard, p.y, p.x, step + 1); }}// To determine if the horse has completed the task, compare step with the number of steps that should be taken,
// If the number is not reached, the task is not completed and the entire board is set to 0
Step < X * Y; step < X * Y
//1. The chessboard has not finished yet
//2. The board is in a backtracking process
if(step < X * Y && ! finished) { chessboard[row][column] =0;
visited[row * X + column] = false;
} else {
finished = true; }}/** * Function: based on the current position (Point object), calculate what other positions (Point) the horse can go, and put into a collection (ArrayList), up to 8 positions **@param curPoint
* @return* /
public static ArrayList<Point> next(Point curPoint) {
// Create an ArrayList
ArrayList<Point> ps = new ArrayList<Point>();
// Create a Point
Point p1 = new Point();
// Indicates that the horse can walk 5
if ((p1.x = curPoint.x - 2) > =0 && (p1.y = curPoint.y - 1) > =0) {
ps.add(new Point(p1));
}
// Determine the horse can go 6 position
if ((p1.x = curPoint.x - 1) > =0 && (p1.y = curPoint.y - 2) > =0) {
ps.add(new Point(p1));
}
// Determine the horse can go 7 position
if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) > =0) {
ps.add(new Point(p1));
}
// Determine that the horse can go to position 0
if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) > =0) {
ps.add(new Point(p1));
}
// Determine the horse can go 1 position
if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
ps.add(new Point(p1));
}
// Determine the horse can go 2 position
if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
ps.add(new Point(p1));
}
// Determine the horse can go 3 position
if ((p1.x = curPoint.x - 1) > =0 && (p1.y = curPoint.y + 2) < Y) {
ps.add(new Point(p1));
}
// Determine the horse can go 4 position
if ((p1.x = curPoint.x - 2) > =0 && (p1.y = curPoint.y + 1) < Y) {
ps.add(new Point(p1));
}
return ps;
}
/** * A non-descending sort is performed based on all the next selected positions of the current step to reduce the number of backtracking *@param ps
*/
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
// get the number of next positions of o1
int count1 = next(o1).size();
// Get the next number of positions to O2
int count2 = next(o2).size();
if (count1 < count2) {
return -1;
} else if (count1 == count2) {
return 0;
} else {
return 1; }}}); }}Copy the code