本文介绍了骑士之旅算法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我想写一个骑士之旅算法有两个数组，ACCESS和电路板。 ACCESS是我使用要弄清楚什么下一步的行动是和董事会是，用户将看到最后的结果数组的数组。我的算法检查发现可用移动的最小数量的平方和去那里。如果碰巧是2具有相同数量的可用动作的可能动作，我发现哪一个是从中心最远（最接近的边界），并移动到该点。该算法应该给出一个完美的64招骑士旅游项目所有的时间，但我通常只能得到大约60的动作，任何人都可以告诉我为什么不给64？
进口的java.util。*;
进口java.io. *;
进口java.text.DecimalFormat中;类KnightsTour
{
公共静态无效的主要（字符串ARGS []）抛出IOException异常
{
布尔hasnextmove = TRUE;
骑士骑士=新耐特（）;
knight.getStart（）;
做
{
knight.move（）;
knight.newposition（）;
hasnextmove = knight.hasnextmove（）;
}而（hasnextmove == TRUE）;
knight.displayBoard（）;
}
}骑士类
{
DecimalFormat的twoDigits =新DecimalFormat的（00）;
私人诠释板[] [];
私人诠释STARTROW，startCol，rowPos，colPos，最小的;
私人INT K = 2;
私人布尔此举= TRUE;
最终私人INT ACCESS [] [] = {{0，0，0，0，0，0，0，0，0，0，0，0}，
{0，0，0，0，0，0，0，0，0，0，0，0}，
{0,0，2，3，4，4，4，4，3，2，0，0}，
{0，0，3，4，6,6，6,6，4,3，0，0}，
{0，0，4，6，8，8,8，8,6，4，0，0}，
{0，0，4，6，8，8,8，8,6，4，0，0}，
{0，0，4，6，8，8,8，8,6，4，0，0}，
{0，0，4，6，8，8,8，8,6，4，0，0}，
{0，0，3，4，6,6，6,6，4,3，0，0}，
{0,0，2，3，4，4，4，4，3，2，0，0}，
{0，0，0，0，0，0，0，0，0，0，0，0}，
{0，0，0，0，0，0，0，0，0，0，0，0}};
//构造函数，初始化值和董事会
公共骑士（）
{
板=新INT [8] [8];
的for（int i = 0; I＆LT; 8;我++）
对于（INT K = 0; K＆LT; 8; k ++）
板[I] [K] = 0;
STARTROW = 0;
startCol = 0;
rowPos = 0;
colPos = 0;
}
//测试，以查看是否有其他可用的举动
公共布尔hasnextmove（）
{
！如果（ACCESS [rowPos + 1] [colPos + 2] = 0 || ACCESS [rowPos + 1] [colPos - 2]！= 0 || ACCESS [rowPos - 1] [colPos + 2] = 0 ||！ ACCESS [rowPos - 1] [colPos - 2]！= 0 || ACCESS [rowPos - 2]！[colPos + 1] = 0 || ACCESS [rowPos - 2] [colPos - 1]！= 0 || ACCESS [ rowPos + 2] [colPos！ - 1] = 0 || ACCESS [rowPos + 2] [colPos + 1] = 0）
返回true;
其他
返回false;
}
//获取用户输入开始骑士广场
公共无效getStart（）抛出IOException异常
{
扫描仪输入=新的扫描仪（System.in）;
的System.out.println（请输入骑士的起始行数：）;
STARTROW = input.nextInt（）+ 1;
的System.out.println（请输入骑士的起始列数：）;
startCol = input.nextInt（）+ 1;
rowPos = STARTROW;
colPos = startCol;
板[STARTROW - 2] [startCol - 2] = 1;
ACCESS [STARTROW] [startCol] = 0;
}
//显示板
公共无效displayBoard（）
{
的System.out.println（这是游戏板）;
的for（int i = 0; I＆LT; 8;我++）
{
对于（INT K = 0; K＆LT; 8; k ++）
{
System.out.print（twoDigits.format（板[I] [K]）+）;
}
的System.out.println（）;
}
}
//看到如果有可能的举动，如果是这样，什么是最小号的空间，骑士可以移动
公共无效移动（）
{
最小= 50; ！如果（ACCESS [rowPos + 1] [colPos + 2] = 0 || ACCESS [rowPos + 1] [colPos - 2]！= 0 || ACCESS [rowPos - 1] [colPos + 2] = 0 ||！ ACCESS [rowPos - 1] [colPos - 2]！= 0 || ACCESS [rowPos - 2]！[colPos + 1] = 0 || ACCESS [rowPos - 2] [colPos - 1]！= 0 || ACCESS [ rowPos + 2] [colPos！ - 1] = 0 || ACCESS [rowPos + 2] [colPos + 1] = 0）
此举= TRUE;
其他
此举= FALSE; 如果（移动==真）
{
如果（ACCESS [rowPos + 1] [colPos + 2]所述;最小和放大器;＆放大器;！ACCESS [rowPos + 1] [colPos + 2] = 0）
最小= ACCESS [rowPos + 1] [colPos + 2]; 如果（ACCESS [rowPos + 1] [colPos - 2]所述;最小和放大器;＆放大器;！ACCESS [rowPos + 1] [colPos - 2] = 0）
最小= ACCESS [rowPos + 1] [colPos - 2]; 如果（ACCESS [rowPos - 1] [colPos + 2]所述;最小和放大器;＆放大器;！ACCESS [rowPos - 1] [colPos + 2] = 0）
最小= ACCESS [rowPos - 1] [colPos + 2]; 如果（ACCESS [rowPos - 1] [colPos - 2]所述;最小和放大器;＆放大器;！ACCESS [rowPos - 1] [colPos - 2] = 0）
最小= ACCESS [rowPos - 1] [colPos - 2]; 如果（ACCESS [rowPos + 2] [colPos + 1];最小和放大器;＆放大器;！ACCESS [rowPos + 2] [colPos + 1] = 0）
最小= ACCESS [rowPos + 2] [colPos + 1]; 如果（ACCESS [rowPos + 2] [colPos - 1];最小和放大器;＆放大器;！ACCESS [rowPos + 2] [colPos - 1] = 0）
最小= ACCESS [rowPos + 2] [colPos - 1]; 如果（ACCESS [rowPos - 2] [colPos + 1];最小和放大器;＆放大器;！ACCESS [rowPos - 2] [colPos + 1] = 0）
最小= ACCESS [rowPos - 2] [colPos + 1]; 如果（ACCESS [rowPos - 2] [colPos - 1];最小和放大器;＆放大器;！ACCESS [rowPos - 2] [colPos - 1] = 0）
最小= ACCESS [rowPos - 2] [colPos - 1];
}
}
//移动骑士到最小编号的方形它可以
公共无效在newPosition（）
{
INT temprow = rowPos;
INT tempcol = colPos;
INT possiblemoves = 0;
布尔移动= FALSE;
布尔specialcasemoved = FALSE;
//移动件新点
如果（ACCESS [rowPos - 2] [colPos + 1] ==最小和放大器;＆放大器;移动==假）
{
temprow = rowPos - 2;
tempcol = colPos + 1;
possiblemoves ++;
}
如果（ACCESS [rowPos - 1] [colPos + 2] ==最小和放大器;＆放大器;移动==假）
{
temprow = rowPos - 1;
tempcol = colPos + 2;
possiblemoves ++;
}
如果（ACCESS [rowPos + 1] [colPos + 2] ==最小和放大器;＆放大器;移动==假）
{
temprow = rowPos + 1;
tempcol = colPos + 2;
possiblemoves ++;
}
如果（ACCESS [rowPos + 2] [colPos + 1] ==最小和放大器;＆放大器;移动==假）
{
temprow = rowPos + 2;
tempcol = colPos + 1;
possiblemoves ++;
}
如果（ACCESS [rowPos + 2] [colPos - 1] ==最小和放大器;＆放大器;移动==假）
{
temprow = rowPos + 2;
tempcol = colPos - 1;
possiblemoves ++;
}
如果（ACCESS [rowPos + 1] [colPos - 2] ==最小和放大器;＆放大器;移动==假）
{
temprow = rowPos + 1;
tempcol = colPos - 2;
possiblemoves ++;
}
如果（ACCESS [rowPos - 1] [colPos - 2] ==最小和放大器;＆放大器;移动==假）
{
temprow = rowPos - 1;
tempcol = colPos - 2;
possiblemoves ++;
}
如果（ACCESS [rowPos - 2] [colPos - 1] ==最小和放大器;＆放大器;移动==假）
{
temprow = rowPos - 2;
tempcol = colPos - 1;
possiblemoves ++;
}
如果（possiblemoves→1）
{
双距离= 0;
双tempdistance;
如果（ACCESS [rowPos - 2] [colPos + 1] ==最小）
{
tempdistance =的Math.sqrt（Math.pow（（6.5 - （rowPos - 2 - 1）），2）+ Math.pow（（6.5 - （colPos + 1 - 1）），2））;
如果（tempdistance＆GT;距离）
{
距离= tempdistance;
temprow = rowPos - 2;
tempcol = colPos + 1;
}
}
如果（ACCESS [rowPos - 1] [colPos + 2] ==最小）
{
tempdistance =的Math.sqrt（Math.pow（（6.5 - （rowPos - 1 - 1）），2）+ Math.pow（（6.5 - （colPos + 2 - 1）），2））;
如果（tempdistance＆GT;距离）
{
距离= tempdistance;
temprow = rowPos - 1;
tempcol = colPos + 2;
}
}
如果（ACCESS [rowPos + 1] [colPos + 2] ==最小）
{
tempdistance =的Math.sqrt（Math.pow（（6.5 - （rowPos + 1 - 1）），2）+ Math.pow（（6.5 - （colPos + 2 - 1）），2））;
如果（tempdistance＆GT;距离）
{
距离= tempdistance;
temprow = rowPos + 1;
tempcol = colPos + 2;
}
}
如果（ACCESS [rowPos +2] [colPos + 1] ==最小）
{
tempdistance =的Math.sqrt（Math.pow（（6.5 - （rowPos + 2 - 1）），2）+ Math.pow（（6.5 - （colPos + 1 - 1）），2））;
如果（tempdistance＆GT;距离）
{
距离= tempdistance;
temprow = rowPos + 2;
tempcol = colPos + 1;
}
}
如果（ACCESS [rowPos + 2] [colPos - 1] ==最小）
{
tempdistance =的Math.sqrt（Math.pow（（6.5 - （rowPos + 2 - 1）），2）+ Math.pow（（6.5 - （colPos - 1 - 1）），2））;
如果（tempdistance＆GT;距离）
{
距离= tempdistance;
temprow = rowPos + 2;
tempcol = colPos - 1;
}
}
如果（ACCESS [rowPos + 1] [colPos - 2] ==最小）
{
tempdistance =的Math.sqrt（Math.pow（（6.5 - （rowPos + 1 - 1）），2）+ Math.pow（（6.5 - （colPos - 2 - 1）），2））;
如果（tempdistance＆GT;距离）
{
距离= tempdistance;
temprow = rowPos + 1;
tempcol = colPos - 2;
}
}
如果（ACCESS [rowPos - 1] [colPos - 2] ==最小）
{
tempdistance =的Math.sqrt（Math.pow（（6.5 - （rowPos - 1 - 1）），2）+ Math.pow（（6.5 - （colPos - 2 - 1）），2））;
如果（tempdistance＆GT;距离）
{
距离= tempdistance;
temprow = rowPos - 1;
tempcol = colPos - 2;
}
}
如果（ACCESS [rowPos - 2] [colPos - 1] ==最小）
{
tempdistance =的Math.sqrt（Math.pow（（6.5 - （rowPos - 2 - 1）），2）+ Math.pow（（6.5 - （colPos - 1 - 1）），2））;
如果（tempdistance＆GT;距离）
{
距离= tempdistance;
temprow = rowPos - 2;
tempcol = colPos - 1;
}
}
/ *布尔M1，M2，M3，M4，M5，M6，M7，M8;
M1 = M2 = M3 = M4 = M5 M6 = M7 = = = M8假的;
INT randomnumber;
如果（ACCESS [rowPos - 2] [colPos + 1] ==最小）
{
M1 = TRUE;
}
如果（ACCESS [rowPos - 1] [colPos + 2] ==最小）
{
M2 =真实的;
}
如果（ACCESS [rowPos + 1] [colPos + 2] ==最小）
{
M3 = TRUE;
}
如果（ACCESS [rowPos + 2] [colPos + 1] ==最小）
{
M4 = TRUE;
}
如果（ACCESS [rowPos + 2] [colPos - 1] ==最小）
{
M5 = TRUE;
}
如果（ACCESS [rowPos + 1] [colPos - 2] ==最小）
{
M6 = TRUE;
}
如果（ACCESS [rowPos - 1] [colPos - 2] ==最小）
{
M7 = TRUE;
}
如果（ACCESS [rowPos - 2] [colPos - 1] ==最小）
{
M8 = TRUE;
}
做
{
随机兰特=新的随机（）;
INT randomNum =（int）的（rand.nextInt（6）+1）+ 1; 开关（randomNum）
{
情况1：
如果（M1 ==真）
{
temprow = rowPos - 2;
tempcol = colPos + 1;
specialcasemoved = TRUE;
}
案例2：
如果（M2 ==真）
{
temprow = rowPos - 1;
tempcol = colPos + 2;
specialcasemoved = TRUE;
}
案例3：
如果（M3 ==真）
{
temprow = rowPos + 1;
tempcol = colPos + 2;
specialcasemoved = TRUE;
}
情况4：
如果（M4 ==真）
{
temprow = rowPos + 2;
tempcol = colPos + 1;
specialcasemoved = TRUE;
}
情况5：
如果（M5 == true）而
{
temprow = rowPos + 2;
tempcol = colPos - 1;
specialcasemoved = TRUE;
}
情况6：
如果（M6 == true）而
{
temprow = rowPos + 1;
tempcol = colPos - 2;
specialcasemoved = TRUE;
}
案例7：
如果（M7 ==真）
{
temprow = rowPos - 1;
tempcol = colPos - 2;
specialcasemoved = TRUE;
}
案例8：
如果（M8 == true）而
{
temprow = rowPos - 2;
tempcol = colPos - 1;
specialcasemoved = TRUE;
}
}
}而（specialcasemoved ==假）; * /
}
rowPos = temprow;
colPos = tempcol;
的System.out.println（possiblemoves）;
possiblemoves = 0;
ACCESS [rowPos] [colPos] = 0;
板[rowPos - 2] [colPos - 2] = K;
ķ++;
//的System.out.println（rowPos ++ colPos）;
}
}
解决方案
有与60的动作没有骑士旅行解决方案。有64个方格的棋盘上所以骑士旅行必须恰好64移动（或可能是63，如果它不是一个闭环解决方案）。如果你得到60移动的解决方案，然后你的算法被破解。
这可能是你误会Warnsdorff的规则，如果我间preT你的描述字面上。该规则是为了解决一个详尽的骑士旅行算法效率低的问题，由于的可能性的数量。这表明，用详尽，深度时，首先，回溯搜索算法，总是先探讨它本身所具有的选择最少的选项。这仍然需要，因为即使回溯使用规则有时会导致需要备份出来死角。
我知道这可能没有解决您的问题，但你有很多code的发布，这使得它复杂明白到底什么可能会出错。我相信它可以通过更好的封装可以大大简化。我很乐意张贴一些建议，如果这将是有益的 - 只是发表评论
I'm trying to write a Knights Tour Algorithm which has two arrays, ACCESS and board. ACCESS is the array I use to figure out what the next move is and board is the array that the user will see as the end result. My algorithm checks to find the square with the smallest number of available moves and goes there. If there happen to be 2 possible moves with the same number of available moves, I find which one is furthest from the center (closest to the boundaries) and move to that spot. This algorithm SHOULD give a perfect 64 move knights tour program all the time but I usually only get about 60 moves, can anyone tell me why it doesn't give 64?
import java.util.*;
import java.io.*;
import java.text.DecimalFormat;
class KnightsTour
{
public static void main(String args[]) throws IOException
{
boolean hasnextmove = true;
Knight knight = new Knight();
knight.getStart();
do
{
knight.move();
knight.newposition();
hasnextmove = knight.hasnextmove();
}while(hasnextmove == true);
knight.displayBoard();
}
}
class Knight
{
DecimalFormat twoDigits = new DecimalFormat("00");
private int board[][];
private int startRow, startCol, rowPos, colPos, smallest;
private int k = 2;
private boolean move = true;
final private int ACCESS[][] = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 2, 3, 4, 4, 4, 4, 3, 2, 0, 0},
{0, 0, 3, 4, 6, 6, 6, 6, 4, 3, 0, 0},
{0, 0, 4, 6, 8, 8, 8, 8, 6, 4, 0, 0},
{0, 0, 4, 6, 8, 8, 8, 8, 6, 4, 0, 0},
{0, 0, 4, 6, 8, 8, 8, 8, 6, 4, 0, 0},
{0, 0, 4, 6, 8, 8, 8, 8, 6, 4, 0, 0},
{0, 0, 3, 4, 6, 6, 6, 6, 4, 3, 0, 0},
{0, 0, 2, 3, 4, 4, 4, 4, 3, 2, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
// constructor, initializes values and the board
public Knight()
{
board = new int[8][8];
for(int i = 0; i < 8; i++)
for(int k = 0; k < 8; k++)
board[i][k] = 0;
startRow = 0;
startCol = 0;
rowPos = 0;
colPos = 0;
}
// tests to see if there is another move available
public boolean hasnextmove()
{
if(ACCESS[rowPos + 1][colPos + 2] != 0 || ACCESS[rowPos + 1][colPos - 2] != 0 || ACCESS[rowPos - 1][colPos + 2] != 0 || ACCESS[rowPos - 1][colPos - 2] != 0 || ACCESS[rowPos - 2][colPos + 1] != 0 || ACCESS[rowPos - 2][colPos - 1] != 0 || ACCESS[rowPos + 2][colPos - 1] != 0 || ACCESS[rowPos + 2][colPos + 1] != 0)
return true;
else
return false;
}
// gets user input for starting square of the knight
public void getStart() throws IOException
{
Scanner input = new Scanner(System.in);
System.out.println("Please input the starting row number of the knight: ");
startRow = input.nextInt() + 1;
System.out.println("Please input the starting column number of the knight: ");
startCol = input.nextInt() + 1;
rowPos = startRow;
colPos = startCol;
board[startRow - 2][startCol - 2] = 1;
ACCESS[startRow][startCol] = 0;
}
// displays the board
public void displayBoard()
{
System.out.println("This is the game board");
for(int i = 0; i < 8; i++)
{
for(int k = 0; k < 8; k++)
{
System.out.print(twoDigits.format(board[i][k]) + " ");
}
System.out.println();
}
}
// sees if there is a possible move and if so, what is the smallest number space that the knight can move
public void move()
{
smallest = 50;
if(ACCESS[rowPos + 1][colPos + 2] != 0 || ACCESS[rowPos + 1][colPos - 2] != 0 || ACCESS[rowPos - 1][colPos + 2] != 0 || ACCESS[rowPos - 1][colPos - 2] != 0 || ACCESS[rowPos - 2][colPos + 1] != 0 || ACCESS[rowPos - 2][colPos - 1] != 0 || ACCESS[rowPos + 2][colPos - 1] != 0 || ACCESS[rowPos + 2][colPos + 1] != 0)
move = true;
else
move = false;
if(move == true)
{
if(ACCESS[rowPos + 1][colPos + 2] < smallest && ACCESS[rowPos + 1][colPos + 2] != 0)
smallest = ACCESS[rowPos + 1][colPos + 2];
if(ACCESS[rowPos + 1][colPos - 2] < smallest && ACCESS[rowPos + 1][colPos - 2] != 0)
smallest = ACCESS[rowPos + 1][colPos - 2];
if(ACCESS[rowPos - 1][colPos + 2] < smallest && ACCESS[rowPos - 1][colPos + 2] != 0)
smallest = ACCESS[rowPos - 1][colPos + 2];
if(ACCESS[rowPos - 1][colPos - 2] < smallest && ACCESS[rowPos - 1][colPos - 2] != 0)
smallest = ACCESS[rowPos - 1][colPos - 2];
if(ACCESS[rowPos + 2][colPos + 1] < smallest && ACCESS[rowPos + 2][colPos + 1] != 0)
smallest = ACCESS[rowPos + 2][colPos + 1];
if(ACCESS[rowPos + 2][colPos - 1] < smallest && ACCESS[rowPos + 2][colPos - 1] != 0)
smallest = ACCESS[rowPos + 2][colPos - 1];
if(ACCESS[rowPos - 2][colPos + 1] < smallest && ACCESS[rowPos - 2][colPos + 1] != 0)
smallest = ACCESS[rowPos - 2][colPos + 1];
if(ACCESS[rowPos - 2][colPos - 1] < smallest && ACCESS[rowPos - 2][colPos - 1] != 0)
smallest = ACCESS[rowPos - 2][colPos - 1];
}
}
// moves the knight to the smallest numbered square it can
public void newposition()
{
int temprow = rowPos;
int tempcol = colPos;
int possiblemoves = 0;
boolean moved = false;
boolean specialcasemoved = false;
// moves pieces to new spot
if(ACCESS[rowPos - 2][colPos + 1] == smallest && moved == false)
{
temprow = rowPos - 2;
tempcol = colPos + 1;
possiblemoves++;
}
if(ACCESS[rowPos - 1][colPos + 2] == smallest && moved == false)
{
temprow = rowPos - 1;
tempcol = colPos + 2;
possiblemoves++;
}
if(ACCESS[rowPos + 1][colPos + 2] == smallest && moved == false)
{
temprow = rowPos + 1;
tempcol = colPos + 2;
possiblemoves++;
}
if(ACCESS[rowPos + 2][colPos + 1] == smallest && moved == false)
{
temprow = rowPos + 2;
tempcol = colPos + 1;
possiblemoves++;
}
if(ACCESS[rowPos + 2][colPos - 1] == smallest && moved == false)
{
temprow = rowPos + 2;
tempcol = colPos - 1;
possiblemoves++;
}
if(ACCESS[rowPos + 1][colPos - 2] == smallest && moved == false)
{
temprow = rowPos + 1;
tempcol = colPos - 2;
possiblemoves++;
}
if(ACCESS[rowPos - 1][colPos - 2] == smallest && moved == false)
{
temprow = rowPos - 1;
tempcol = colPos - 2;
possiblemoves++;
}
if(ACCESS[rowPos - 2][colPos - 1] == smallest && moved == false)
{
temprow = rowPos - 2;
tempcol = colPos - 1;
possiblemoves++;
}
if(possiblemoves > 1)
{
double distance = 0;
double tempdistance;
if(ACCESS[rowPos - 2][colPos + 1] == smallest)
{
tempdistance = Math.sqrt(Math.pow((6.5 - (rowPos - 2 - 1)), 2) + Math.pow((6.5 - (colPos + 1 - 1)), 2));
if(tempdistance > distance)
{
distance = tempdistance;
temprow = rowPos - 2;
tempcol = colPos + 1;
}
}
if(ACCESS[rowPos - 1][colPos + 2] == smallest)
{
tempdistance = Math.sqrt(Math.pow((6.5 - (rowPos - 1 - 1)), 2) + Math.pow((6.5 - (colPos + 2 - 1)), 2));
if(tempdistance > distance)
{
distance = tempdistance;
temprow = rowPos - 1;
tempcol = colPos + 2;
}
}
if(ACCESS[rowPos + 1][colPos + 2] == smallest)
{
tempdistance = Math.sqrt(Math.pow((6.5 - (rowPos + 1 - 1)), 2) + Math.pow((6.5 - (colPos + 2 - 1)), 2));
if(tempdistance > distance)
{
distance = tempdistance;
temprow = rowPos + 1;
tempcol = colPos + 2;
}
}
if(ACCESS[rowPos +2][colPos + 1] == smallest)
{
tempdistance = Math.sqrt(Math.pow((6.5 - (rowPos + 2 - 1)), 2) + Math.pow((6.5 - (colPos + 1 - 1)), 2));
if(tempdistance > distance)
{
distance = tempdistance;
temprow = rowPos + 2;
tempcol = colPos + 1;
}
}
if(ACCESS[rowPos + 2][colPos - 1] == smallest)
{
tempdistance = Math.sqrt(Math.pow((6.5 - (rowPos + 2 - 1)), 2) + Math.pow((6.5 - (colPos - 1 - 1)), 2));
if(tempdistance > distance)
{
distance = tempdistance;
temprow = rowPos + 2;
tempcol = colPos - 1;
}
}
if(ACCESS[rowPos + 1][colPos - 2] == smallest)
{
tempdistance = Math.sqrt(Math.pow((6.5 - (rowPos + 1 - 1)), 2) + Math.pow((6.5 - (colPos - 2 - 1)), 2));
if(tempdistance > distance)
{
distance = tempdistance;
temprow = rowPos + 1;
tempcol = colPos - 2;
}
}
if(ACCESS[rowPos - 1][colPos - 2] == smallest)
{
tempdistance = Math.sqrt(Math.pow((6.5 - (rowPos - 1 - 1)), 2) + Math.pow((6.5 - (colPos - 2 - 1)), 2));
if(tempdistance > distance)
{
distance = tempdistance;
temprow = rowPos - 1;
tempcol = colPos - 2;
}
}
if(ACCESS[rowPos - 2][colPos - 1] == smallest)
{
tempdistance = Math.sqrt(Math.pow((6.5 - (rowPos - 2 - 1)), 2) + Math.pow((6.5 - (colPos - 1 - 1)), 2));
if(tempdistance > distance)
{
distance = tempdistance;
temprow = rowPos - 2;
tempcol = colPos - 1;
}
}
/* boolean m1, m2, m3, m4, m5, m6, m7, m8;
m1 = m2 = m3 = m4 = m5 = m6 = m7 = m8 = false;
int randomnumber;
if(ACCESS[rowPos - 2][colPos + 1] == smallest)
{
m1 = true;
}
if(ACCESS[rowPos - 1][colPos + 2] == smallest)
{
m2 = true;
}
if(ACCESS[rowPos + 1][colPos + 2] == smallest)
{
m3 = true;
}
if(ACCESS[rowPos + 2][colPos + 1] == smallest)
{
m4 = true;
}
if(ACCESS[rowPos + 2][colPos - 1] == smallest)
{
m5 = true;
}
if(ACCESS[rowPos + 1][colPos - 2] == smallest)
{
m6 = true;
}
if(ACCESS[rowPos - 1][colPos - 2] == smallest)
{
m7 = true;
}
if(ACCESS[rowPos - 2][colPos - 1] == smallest)
{
m8 = true;
}
do
{
Random rand = new Random();
int randomNum = (int) (rand.nextInt(6)+1) + 1;
switch(randomNum)
{
case 1:
if(m1 == true)
{
temprow = rowPos - 2;
tempcol = colPos + 1;
specialcasemoved = true;
}
case 2:
if(m2 == true)
{
temprow = rowPos - 1;
tempcol = colPos + 2;
specialcasemoved = true;
}
case 3:
if(m3 == true)
{
temprow = rowPos + 1;
tempcol = colPos + 2;
specialcasemoved = true;
}
case 4:
if(m4 == true)
{
temprow = rowPos + 2;
tempcol = colPos + 1;
specialcasemoved = true;
}
case 5:
if(m5 == true)
{
temprow = rowPos + 2;
tempcol = colPos - 1;
specialcasemoved = true;
}
case 6:
if(m6 == true)
{
temprow = rowPos + 1;
tempcol = colPos - 2;
specialcasemoved = true;
}
case 7:
if(m7 == true)
{
temprow = rowPos - 1;
tempcol = colPos - 2;
specialcasemoved = true;
}
case 8:
if(m8 == true)
{
temprow = rowPos - 2;
tempcol = colPos - 1;
specialcasemoved = true;
}
}
}while(specialcasemoved == false);*/
}
rowPos = temprow;
colPos = tempcol;
System.out.println(possiblemoves);
possiblemoves = 0;
ACCESS[rowPos][colPos] = 0;
board[rowPos - 2][colPos - 2] = k;
k++;
// System.out.println(rowPos + " " + colPos);
}
}
解决方案
There is no Knight's Tour solution with 60 moves. There are 64 squares on a chess board so a Knight's Tour must have exactly 64 moves (or possibly 63 if it's not a closed loop solution). If you get a solution with 60 moves then your algorithm is broken.
It is possible that you have misunderstood Warnsdorff's rule if I interpret your description literally. The 'rule' is intended to solve the problem of an exhaustive Knight's Tour algorithm being inefficient due to the number of possibilities. It suggests that when using an exhaustive, depth first, backtracking search algorithm, always explore first the option which itself has the fewest options. This still requires backtracking as even using the rule will sometimes lead to dead ends that need to be backed out of.
I realise this might not have solved your problem but you have a lot of code posted which makes it complicated to understand exactly what might be going wrong. I believe it can be substantially simplified through better encapsulation. I'd be happy to post some suggestions if it would be helpful - just leave a comment.
这篇关于骑士之旅算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！