騎士走棋盤java,c實(shí)現(xiàn)

1、From GossipcaterpillarAlgorithm Gossip:騎士走棋盤說明騎士旅遊(Knight tour )在十八世紀(jì)初倍受數(shù)學(xué)家與拼圖迷的注意，它什麼時(shí)候被提岀已不可考，騎士的走法為西洋棋的走法，騎士可以由任一個(gè)位置岀發(fā)，它要如何走完所有的位置？解法騎士的走法，基本上可以使用遞迴來解決，但是純綷的遞迴在維度大時(shí)相當(dāng)沒有效率，一個(gè)聰明的解法由J.C. Warnsdorff在1823年提岀，簡單的說，先將最難的位置走完，接下來的路就寬廣 了，騎士所要走的下一步，為下一步再選擇時(shí)，所能走的步數(shù)最少的一步。，使用這個(gè)方法，在不使用遞迴的情況下，可以有較高的機(jī)率找岀走法(找不到走法

2、的機(jī)會(huì)也是有的)。演算法FOR(m = 2; m <= 總步數(shù)；m+)測試下一步可以走的八個(gè)方向，記錄可停留的格數(shù)cou ntIF(cou nt = 0)遊歷失敗ELSE IF(cou nt = 1)下一步只有一個(gè)可能ELSE 找出下一步的出路最少的格子如果出路值相同，則選第一個(gè)遇到的出路。走最少出路的格子，記錄騎士的新位置。實(shí)作#i nclude <stdio.h>int board88 = 0;int main(v oid) int startx, starty;int i, j;prin tf("輸入起始點(diǎn)：");scanf("%d %d&

3、quot;, &startx, &starty);if(travel(startx, starty) printf("遊歷完成！ n");else printf("遊歷失??！ n");for(i = 0; i < 8; i+) for(j = 0; j < 8; j+) prin tf("%2d ", boardij); putchar('n');return 0;int travel( int x, int y) /對應(yīng)騎士可走的八個(gè)方向int ktmove18 = -2, -1,1,2,

4、 2,1, -1, -2;int ktmove28 = 1,2, 2, 1, -1, -2, -2, -1;/測試下一步的出路int nexti8 = 0;int nextj8 = 0;/記錄出路的個(gè)數(shù)int exists8 = 0;int i, j, k, m, l;int tmpi, tmpj;int count, min, tmp;i = x;j = y;boardij = 1;for(m = 2; m <= 64; m+) for(l = 0; l < 8; l+) existsl = 0;l = 0;/試探八個(gè)方向for(k = 0; k < 8; k+) tmpi

5、 = i + ktmove1k;tmpj = j + ktmove2k;/如果是邊界了，不可走> 7 | tmpj >if(tmpi < 0| tmpj < 0 | tmpi7)con ti nue;/如果這個(gè)方向可走，記錄下來if(boardtmpitmpj = 0) n extil = tmpi;n extjl = tmpj;/可走的方向加一個(gè)I+;count = l;/如果可走的方向?yàn)?個(gè)，返回if(co unt = 0) return 0;else if(co unt = 1) /只有一個(gè)可走的方向/所以直接是最少出路的方向min = 0;else /找出下一個(gè)

6、位置的出路數(shù)for(l = 0; l < cou nt; I+) for(k = 0; k < 8; k+) tmpi = n extil + ktmove1k;tmpj = n extjl + ktmove2k;if(tmpi < 0 | tmpj < 0 |tmpi > 7 | tmpj > 7) con ti nue;if(boardtmpitmpj = 0) existsl+;tmp = exists0;min = 0;/從可走的方向中尋找最少出路的方向for(l = 1; l < count; l+) if(existsl < tmp)

7、 tmp = existsl;min = l;/ 走最少出路的方向i = n exti min;j = n extjmi n;boardij = m;return 1;« Javapublic class Kni ght public boolea n travel( int startX,int startY, i nt叩 board) /對應(yīng)騎士可走的八個(gè)方向in t ktmove1 = -2, -1, 1,2, 2, 1, -1, -2;int ktmove2 = 1,2, 2, 1, -1, -2, -2, -1;/下一步出路的位置in t n exti = new in t

8、board .len gth;in t n extj = new in tboard .len gth;/記錄出路的個(gè)數(shù)in t exists = new in tboard .len gth;int x = startX;int y = startY;boardxy = 1;for(int m = 2; m <= Math.pow(board.length, 2); m+) for(i nt k = 0; k < board .len gth; k+) existsk = 0;int count = 0;/試探八個(gè)方向for(i nt k = 0; k < board .l

9、en gth; k+) int tmpi = x + ktmove1k;int tmpj = y + ktmove2k;/如果是邊界了，不可走if(tmpi < 0 | tmpj < 0 |tmpi > 7 | tmpj > 7) con ti nue;/如果這個(gè)方向可走，記錄下來if(boardtmpitmpj = 0) n extico unt = tmpi;n extjco unt = tmpj;/可走的方向加一個(gè)coun t+;int min = -1;if(co unt = 0) return false;else if(co unt =1) min = 0;

10、else /找出下一個(gè)位置的出路數(shù)for(int l = 0; l< coun t; l+) k+)for(i nt k= 0; k < board .len gth;int tmpi = n extil + ktmove1k;int tmpj = n extjl + ktmove2k;if(tmpi < 0 | tmpj < 0 |tmpi > 7 | tmpj > 7) con ti nue;if(boardtmpitmpj = 0) existsl+;int tmp = exists0;min = 0;/從可走的方向中尋找最少出路的方向for(int

11、l = 1; l < count; l+) if(existsl < tmp) tmp = existsl;min = l;/走最少出路的方向x = n exti min;y = n extjmi n;boardxy = m;return true;public static void main( Stri ng args) in t board = new in t88;Kni ght kni ght = new Kni ght();if(kni (In teger.parsel nt(args0).In teger.parse In t(args1), board) System.out.pri ntln (”遊歷完成！");else System.out.pri ntln (”遊歷失?。?quot;);for(int i = 0; i < board.length; i+) for(int