ACCESSとboardの2つの配列を持つKnightsTourAlgorithmを作成しようとしています。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の動きで解決策を得るならば、あなたのアルゴリズムは壊れています。
私があなたの説明を文字通りに解釈するならば、あなたがワーンズドルフの規則を誤解している可能性があります。「ルール」は、可能性の数が原因で徹底的なナイトツアーアルゴリズムが非効率的であるという問題を解決することを目的としています。徹底的な深さ優先のバックトラッキング検索アルゴリズムを使用する場合は、常に、それ自体が最もオプションが少ないオプションを最初に探索することをお勧めします。ルールを使用しても行き止まりになり、バックアウトする必要がある場合があるため、これにはバックトラックが必要です。
これでは問題が解決しなかったかもしれませんが、多くのコードが投稿されているため、何が問題になっているのかを正確に理解するのが複雑になっています。カプセル化を改善することで、大幅に簡素化できると思います。それが役に立ったら、私はいくつかの提案を投稿させていただきます-コメントを残してください。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加