/*
* 馬踏棋盤問題：(貪婪法求解)
* 棋盤有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的數。
* 否則返回棋子的下個出路的個數
*/
static int wayOut(int x, int y){
int count = 0;
int tx, ty, i;
//判斷是否超出棋盤邊界，該位置是否已經下過
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];
//如果棋子的下個出路可行，則出路數自加一次
if(tx>-1 && tx<8 && ty>-1 && ty<8 && chessboard[tx][ty]==0)
count++;
}
return count;
}
/**
* 按照棋子的下個出路的個數從低到高排序
* @param next 棋子的八個位置的數組
*/
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，則說明每個棋格都走到了，現在只需要打印結果就完了
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個位置的數組
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;
//循環得到下個棋子N處位置的下個出路的個數
next[i].wayOutNum = wayOut(temp.x, temp.y);
}
//配合貪婪算法，按下個棋子的下個出路數排序後，next[0]就是下個出路數最少的那個
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++,又循環...... */
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);
}
}