骑士游算法
Knights Tour Algorithm
我正在尝试编写一个 Knights Tour 算法，它有两个数组，ACCESS 和 board。 ACCESS 是我用来确定下一步行动的数组，board 是用户将看到的最终结果数组。我的算法会检查以找到可用移动次数最少的方格，然后去那里。如果碰巧有 2 个可能的动作且可用动作的数量相同，我会找到离中心最远（最接近边界）的那个并移动到那个位置。这个算法应该一直给出一个完美的 64 步骑士巡回赛程序，但我通常只能得到大约 60 步，谁能告诉我为什么它不给出 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);
}
}
没有 60 步的骑士之旅解决方案。棋盘上有 64 个方格，因此骑士巡回赛必须恰好有 64 步（如果不是闭环解决方案，则可能为 63 步）。如果你得到一个 60 步的解决方案，那么你的算法就坏了。
如果我从字面上解释您的描述，您可能误解了 Warnsdorff 规则。 'rule' 旨在解决详尽的 Knight's Tour 算法由于可能性的数量而效率低下的问题。它建议在使用详尽的、深度优先的回溯搜索算法时，始终首先探索本身具有最少选项的选项。这仍然需要回溯，因为即使使用该规则有时也会导致需要回溯的死胡同。
我知道这可能没有解决您的问题，但是您有很多代码 posted，这使得准确理解可能出了什么问题变得很复杂。我相信通过更好的封装可以大大简化它。如果有帮助，我很乐意 post 提出一些建议 - 请发表评论。
我正在尝试编写一个 Knights Tour 算法，它有两个数组，ACCESS 和 board。 ACCESS 是我用来确定下一步行动的数组，board 是用户将看到的最终结果数组。我的算法会检查以找到可用移动次数最少的方格，然后去那里。如果碰巧有 2 个可能的动作且可用动作的数量相同，我会找到离中心最远（最接近边界）的那个并移动到那个位置。这个算法应该一直给出一个完美的 64 步骑士巡回赛程序，但我通常只能得到大约 60 步，谁能告诉我为什么它不给出 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);
}
}
没有 60 步的骑士之旅解决方案。棋盘上有 64 个方格，因此骑士巡回赛必须恰好有 64 步（如果不是闭环解决方案，则可能为 63 步）。如果你得到一个 60 步的解决方案，那么你的算法就坏了。
如果我从字面上解释您的描述，您可能误解了 Warnsdorff 规则。 'rule' 旨在解决详尽的 Knight's Tour 算法由于可能性的数量而效率低下的问题。它建议在使用详尽的、深度优先的回溯搜索算法时，始终首先探索本身具有最少选项的选项。这仍然需要回溯，因为即使使用该规则有时也会导致需要回溯的死胡同。
我知道这可能没有解决您的问题，但是您有很多代码 posted，这使得准确理解可能出了什么问题变得很复杂。我相信通过更好的封装可以大大简化它。如果有帮助，我很乐意 post 提出一些建议 - 请发表评论。