java實現馬踏棋盤的完整版
本文實例為大傢分享瞭java實現馬踏棋盤的具體代碼,供大傢參考,具體內容如下
馬踏棋盤很好實現,但有時運行起來特別慢,還可能出不來結果,在這裡要用到貪心算法來優化,即找出最難走的路徑,也就是下下步可下棋的位置最少。
下面給出該算法完整代碼:
/* * 馬踏棋盤問題:(貪婪法求解) * 棋盤有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); } }
這裡給出運算結果:
以上就是本文的全部內容,希望對大傢的學習有所幫助,也希望大傢多多支持WalkonNet。
推薦閱讀:
- java實現馬踏棋盤遊戲
- java實現馬踏棋盤的算法
- java數據結構與算法之馬踏棋盤
- Java基礎題新手練習(三)
- java數組算法例題代碼詳解(冒泡排序,選擇排序,找最大值、最小值,添加、刪除元素等)