ACCESS と board の 2 つの配列を持つ Knights Tour Algorithm を作成しようとしています。ACCESS は次の手が何であるかを把握するために使用する配列であり、board はユーザーが最終結果として見る配列です。私のアルゴリズムは、利用可能な動きの数が最も少ない正方形を見つけるためにチェックし、そこに行きます。利用可能な手数が同じである可能性のある手が 2 つある場合、どちらが中心から最も遠い (境界に最も近い) かを見つけて、その場所に移動します。このアルゴリズムは、常に完璧な 64 回の手のナイツ ツアー プログラムを提供する必要がありますが、私は通常、約 60 回の動きしか得られません。
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);
}
}