/*
? ? ?* 馬踏棋盤問題：(貪婪法求解)
? ? ?* 棋盤有64個位置，“日”字走法，剛好走滿整個棋盤
? ? ?*/

? ? //下一個走法的方向類
? ? class Direction{
? ? ? ? int x;
? ? ? ? int y;
? ? ? ? int wayOutNum;
? ? }

? ? public class Hores_chessboard_1 {
? ? ? ? static final int[] dx = { -2, -1, 1, 2, 2, 1, -1, -2 }; // x方向的增量 ?
? ? ? ? static final int[] dy = { 1, 2, 2, 1, -1, -2, -2, -1 }; // y方向的增量 ?
? ? ? ? static final int N = 8; ? ??
? ? ? ? static int[][] chessboard = new int[N][N]; // 棋盤?

? ? /**
? ? ?*?
? ? ?* @param nami
? ? ?* @param x,y為棋子的位置
? ? ?* @return 如果棋子的位置不合法，則返回一個大于8的數(shù)。
? ? ?* 否則返回棋子的下個出路的個數(shù)
? ? ?*/
? ? static int wayOut(int x, int y){ ? ? ? ?
? ? ? ? int count = 0;
? ? ? ? int tx, ty, i;
? ? ? ? //判斷是否超出棋盤邊界，該位置是否已經(jīng)下過
? ? ? ? if(x<0 || x>7 || y<0 || y>7 || chessboard[x][y]!=0){
? ? ? ? ? ? return 9;
? ? ? ? }
? ? ? ? for(i=0; i<N; i++){
? ? ? ? ? ? tx = x+dx[i];
? ? ? ? ? ? ty = y+dy[i];
? ? ? ? ? ? //如果棋子的下個出路可行，則出路數(shù)自加一次
? ? ? ? ? ? if(tx>-1 && tx<8 && ty>-1 && ty<8 && chessboard[tx][ty]==0)
? ? ? ? ? ? ? ? count++;
? ? ? ? }
? ? ? ? return count;
? ? }

? ? /**
? ? ?* 按照棋子的下個出路的個數(shù)從低到高排序
? ? ?* @param next 棋子的八個位置的數(shù)組
? ? ?*/
? ? static void sort(Direction[] next){
? ? ? ? int i, j, index;
? ? ? ? Direction temp = null;
? ? ? ? //這里用的選擇排序
? ? ? ? for(i=0; i<N; i++){
? ? ? ? ? ? index = i;
? ? ? ? ? ? for(j=i+1; j<N; j++){
? ? ? ? ? ? ? ? if(next[index].wayOutNum > next[j].wayOutNum)
? ? ? ? ? ? ? ? ? ? index = j;
? ? ? ? ? ? }
? ? ? ? ? ? if(i != index){
? ? ? ? ? ? ? ? temp = next[i];
? ? ? ? ? ? ? ? next[i] = next[index];
? ? ? ? ? ? ? ? next[index] = temp;
? ? ? ? ? ? }
? ? ? ? }
? ? }

? ? static void Move(int x, int y, int step){
? ? ? ? int i, j;
? ? ? ? int tx, ty;
? ? ? ? //如果step==64，則說明每個棋格都走到了，現(xiàn)在只需要打印結(jié)果就完了
? ? ? ? if(step == N*N){
? ? ? ? ? ? for(i=0; i<N; i++){
? ? ? ? ? ? ? ? for(j=0; j<N; j++){
? ? ? ? ? ? ? ? ? ? System.out.printf("%3d", chessboard[i][j]);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? System.out.println();
? ? ? ? ? ? }
? ? ? ? ? ? System.exit(0);
? ? ? ? }

? ? ? ? //下一個棋子的N個位置的數(shù)組
? ? ? ? Direction[] next = new Direction[N];

? ? ? ? for(i=0; i<N; i++){
? ? ? ? ? ? Direction temp = new Direction();
? ? ? ? ? ? temp.x = x+dx[i];
? ? ? ? ? ? temp.y = y+dy[i];
? ? ? ? ? ? next[i] = temp;
? ? ? ? ? ? //循環(huán)得到下個棋子N處位置的下個出路的個數(shù)
? ? ? ? ? ? next[i].wayOutNum = wayOut(temp.x, temp.y);
? ? ? ? }

? ? ? ? //配合貪婪算法，按下個棋子的下個出路數(shù)排序后，next[0]就是下個出路數(shù)最少的那個
? ? ? ? sort(next);

? ? ? ? for(i=0; i<N; i++){
? ? ? ? ? ? tx = next[i].x;
? ? ? ? ? ? ty = next[i].y;
? ? ? ? ? ? chessboard[tx][ty] = step;
? ? ? ? ? ? Move(tx, ty, step+1);
? ? ? ? ? ? /*如果上面Move()往下一步走不通，則回溯到這里
? ? ? ? ? ? 重置chessboard[tx][ty]為0，接著i++,又循環(huán)...... */
? ? ? ? ? ? chessboard[tx][ty] = 0;
? ? ? ? }
? ? }

? ? public static void main(String[] args) {
? ? ? ? int i, j;
? ? ? ? //初始化棋盤
? ? ? ? for(i=0; i<8; i++){
? ? ? ? ? ? for(j=0; j<8; j++){
? ? ? ? ? ? ? ? chessboard[i][j] = 0;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? System.out.println("請輸入棋子開始位置（0-7）：");
? ? ? ? Scanner sc = new Scanner(System.in);
? ? ? ? int x = sc.nextInt();
? ? ? ? int y = sc.nextInt();
? ? ? ? //第一步不用比較，賦值第一步
? ? ? ? chessboard[x][y] = 1;
? ? ? ? Move(x, y, 2); ? ? ?
? ? }
}