java實(shí)現(xiàn)馬踏棋盤的完整版
本文實(shí)例為大家分享了java實(shí)現(xiàn)馬踏棋盤的具體代碼,供大家參考,具體內(nèi)容如下
馬踏棋盤很好實(shí)現(xiàn),但有時(shí)運(yùn)行起來(lái)特別慢,還可能出不來(lái)結(jié)果,在這里要用到貪心算法來(lái)優(yōu)化,即找出最難走的路徑,也就是下下步可下棋的位置最少。
下面給出該算法完整代碼:
/* ? ? ?* 馬踏棋盤問(wèn)題:(貪婪法求解) ? ? ?* 棋盤有64個(gè)位置,“日”字走法,剛好走滿整個(gè)棋盤 ? ? ?*/ ? ? //下一個(gè)走法的方向類 ? ? 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 如果棋子的位置不合法,則返回一個(gè)大于8的數(shù)。 ? ? ?* 否則返回棋子的下個(gè)出路的個(gè)數(shù) ? ? ?*/ ? ? static int wayOut(int x, int y){ ? ? ? ? ? ? ? ? int count = 0; ? ? ? ? int tx, ty, i; ? ? ? ? //判斷是否超出棋盤邊界,該位置是否已經(jīng)下過(guò) ? ? ? ? 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]; ? ? ? ? ? ? //如果棋子的下個(gè)出路可行,則出路數(shù)自加一次 ? ? ? ? ? ? if(tx>-1 && tx<8 && ty>-1 && ty<8 && chessboard[tx][ty]==0) ? ? ? ? ? ? ? ? count++; ? ? ? ? } ? ? ? ? return count; ? ? } ? ? /** ? ? ?* 按照棋子的下個(gè)出路的個(gè)數(shù)從低到高排序 ? ? ?* @param next 棋子的八個(gè)位置的數(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,則說(shuō)明每個(gè)棋格都走到了,現(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); ? ? ? ? } ? ? ? ? //下一個(gè)棋子的N個(gè)位置的數(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)得到下個(gè)棋子N處位置的下個(gè)出路的個(gè)數(shù) ? ? ? ? ? ? next[i].wayOutNum = wayOut(temp.x, temp.y); ? ? ? ? } ? ? ? ? //配合貪婪算法,按下個(gè)棋子的下個(gè)出路數(shù)排序后,next[0]就是下個(gè)出路數(shù)最少的那個(gè) ? ? ? ? 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("請(qǐng)輸入棋子開(kāi)始位置(0-7):"); ? ? ? ? Scanner sc = new Scanner(System.in); ? ? ? ? int x = sc.nextInt(); ? ? ? ? int y = sc.nextInt(); ? ? ? ? //第一步不用比較,賦值第一步 ? ? ? ? chessboard[x][y] = 1; ? ? ? ? Move(x, y, 2); ? ? ? ? ? } }
這里給出運(yùn)算結(jié)果:
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
Java?Stream比較兩個(gè)List的差異并取出不同的對(duì)象四種方法
今天開(kāi)發(fā)一個(gè)需求時(shí)要對(duì)A和B兩個(gè)List集合遍歷,并比較出集合A有,而集合B沒(méi)有的值,下面這篇文章主要給大家介紹了關(guān)于Java?Stream比較兩個(gè)List的差異并取出不同對(duì)象的四種方法,需要的朋友可以參考下2024-01-01java selenium教程之selenium詳細(xì)介紹
本文主要介紹Java selenium,這里整理了selenium的一些基本資料,此軟件主要用于Web UI自動(dòng)測(cè)試框架,有興趣的同學(xué)可以看一下2016-08-08解讀Integer類的parseInt和valueOf的區(qū)別
這篇文章主要介紹了解讀Integer類的parseInt和valueOf的區(qū)別,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-11-11基于SpringBoot+Redis的Session共享與單點(diǎn)登錄詳解
這篇文章主要介紹了基于SpringBoot+Redis的Session共享與單點(diǎn)登錄,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-07-07java實(shí)現(xiàn)樹(shù)形菜單對(duì)象
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)樹(shù)形菜單對(duì)象,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-05-05Springboot實(shí)現(xiàn)前后端分離excel下載
這篇文章主要介紹了Springboot實(shí)現(xiàn)前后端分離excel下載,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-11-11