騎士周遊回溯算法

基本介紹

思路

代碼

package com.fly.horse;

import java.awt.*;
import java.util.ArrayList;
import java.util.List;

public class HorseChessboard {
  public static void main(String[] args) {
    X = 6;
    Y = 6;
    int row = 3;
    int column = 4;
    int[][] chessboard = new int[X][Y];
    visited = new boolean[X * Y];
    traversalChessboard(chessboard,row - 1,column - 1,1);

    for(int[] rows : chessboard) {
      for(int step: rows) {
        System.out.print(step + "\t");
      }
      System.out.println();
    }
  }

  private static int X; //棋盤的列數
  private static int Y; //棋盤的行數
  private static boolean[] visited; //是否被通路過
  private static boolean finished;  //是否成功

  /**
   * 根據目前位置(Point對象)，計算馬兒還能走哪些位置(Point)，并放入到一個集合中(ArrayList)
   * @param curPoint 起始位置的對象
   * @return 起始位置可以走的點的對象集合
   */
  public static List<Point> next(Point curPoint) {
    List<Point> points = new ArrayList<>();
    Point point1 = new Point();
    //表示馬兒可以走5這個位置
    if((point1.x = curPoint.x - 2) >= 0 && (point1.y = curPoint.y -1) >= 0) {
      points.add(new Point(point1));
    }
    //判斷馬兒可以走6這個位置
    if((point1.x = curPoint.x - 1) >=0 && (point1.y=curPoint.y-2)>=0) {
      points.add(new Point(point1));
    }
    //判斷馬兒可以走7這個位置
    if ((point1.x = curPoint.x + 1) < X && (point1.y = curPoint.y - 2) >= 0) {
      points.add(new Point(point1));
    }
    //判斷馬兒可以走0這個位置
    if ((point1.x = curPoint.x + 2) < X && (point1.y = curPoint.y - 1) >= 0) {
      points.add(new Point(point1));
    }
    //判斷馬兒可以走1這個位置
    if ((point1.x = curPoint.x + 2) < X && (point1.y = curPoint.y + 1) < Y) {
      points.add(new Point(point1));
    }
    //判斷馬兒可以走2這個位置
    if ((point1.x = curPoint.x + 1) < X && (point1.y = curPoint.y + 2) < Y) {
      points.add(new Point(point1));
    }
    //判斷馬兒可以走3這個位置
    if ((point1.x = curPoint.x - 1) >= 0 && (point1.y = curPoint.y + 2) < Y) {
      points.add(new Point(point1));
    }
    //判斷馬兒可以走4這個位置
    if ((point1.x = curPoint.x - 2) >= 0 && (point1.y = curPoint.y + 1) < Y) {
      points.add(new Point(point1));
    }
    return points;
  }

  /**
   * 根據這個位置的下一步的所有下一步的可以選擇的位置，進行非遞減排序, 減少回溯的次數
   * @param points 一個位置所有可以走的位置的對象集合
   */
  public static void sort(List<Point> points) {
    points.sort((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 0;
      }
    });
  }

  /**
   * @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;
    List<Point> points = next(new Point(column,row));
    sort(points);
    while (!points.isEmpty()) {
      Point point = points.remove(0);
      if (!visited[point.y * X + point.x]) {
        traversalChessboard(chessboard,point.y,point.x,step + 1);
      }
    }
    if (step < X * Y && !finished) {
      chessboard[row][column] = 0;
      visited[row * X + column] = false;
    } else {
      finished = true;
    }
  }

}