Hello,
I know this is a popular problem with a lot of solutions, but I don't want to be pointed to a post by someone else with THEIR solution. I want to figure out how to make my own code work. So, any help you could provide would be wonderful!
So, what I'm trying to do is solve the Knight's Tour problem (without a GUI) and print the result as follows:
Now, of course this is not the correct answer since there are many unvisited squares (denoted by 0's) and many numbers are absent. The numbers are supposed to represent the order of the steps it takes to fill the grid.
Here is my code. It is relatively short so it's worth just following it since I can't pinpoint where the problem is.
And, here's my tester file:
I would really like to get this program running properly. What is frustrating is that I am so sure I have accounted for everything, yet there is obviously still some problem. Thanks in advance!
I know this is a popular problem with a lot of solutions, but I don't want to be pointed to a post by someone else with THEIR solution. I want to figure out how to make my own code work. So, any help you could provide would be wonderful!
So, what I'm trying to do is solve the Knight's Tour problem (without a GUI) and print the result as follows:
[1][0][3][0][0][0][0][0]
[8][0][43][0][0][0][0][0]
[0][2][0][0][0][0][0][0]
[0][18][0][64][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][0][0]
[0][0][0][0][0][0][0][0]
[8][0][43][0][0][0][0][0]
[0][2][0][0][0][0][0][0]
[0][18][0][64][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][0][0]
[0][0][0][0][0][0][0][0]
Here is my code. It is relatively short so it's worth just following it since I can't pinpoint where the problem is.
Code:
import java.util.ArrayList;
public class Knight
{
private int currentX;
private int currentY;
private int tempX;
private int tempY;
private int counter;
private int[][] kmoves = {{1,2},{1,-2},{-1,2},{-1,-2},{2,1},{2,-1},{-2,1},{-2,-1}};
private int[][] board = new int[8][8];
private boolean[][] boolboard = new boolean[8][8];
private ArrayList <Integer> possibleX = new ArrayList();
private ArrayList <Integer> possibleY = new ArrayList();
private int[][] access = {
{2,3,4,4,4,4,3,2},
{3,4,6,6,6,6,4,3},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{3,4,6,6,6,6,4,3},
{2,3,4,4,4,4,3,2}
};
public Knight()
{
currentX = 0;
currentY = 0;
counter = 1;
for(int i = 0; i < 8; i++)
{
for(int j = 0; j < 8; j++)
{
board[i][j] = 0;
}
}
for(int i = 0; i < 8; i++)
{
for(int j = 0; j < 8; j++)
{
boolboard[i][j] = false;
}
}
}
public void getMoveLocations()
{
for(int i = 0; i < kmoves.length; i++)
{
if(currentY + kmoves[i][1] < 8 && currentY + kmoves[i][1] >=0 && currentX + kmoves[i][0] < 8 && currentX + kmoves[i][0] >= 0 && (boolboard[currentY + kmoves[i][1]][currentX + kmoves[i][0]] == false))
{
possibleX.add(currentX + kmoves[i][0]);
possibleY.add(currentY + kmoves[i][1]);
}
}
}
public void selectMoveLocation()
{
int i = 0;
int lowX = 4;
int lowY = 4;
while(i < possibleX.size())
{
if(access[possibleY.get(i)][possibleX.get(i)] <= access[lowY][lowX])
{
lowX = possibleX.get(i);
lowY = possibleY.get(i);
}
i++;
}
int p = 0;
while(p < possibleX.size())
{
access[possibleY.get(p)][possibleX.get(p)]--;
p++;
}
tempX = currentX; //remembers old x value
tempY = currentY; //remembers old y value
currentX = lowX; //x value to move to
currentY = lowY; //y value to move to
}
public void makeMove()
{
board[tempY][tempX] = counter;
boolboard[tempY][tempX] = true;
counter++;
}
public void printBoard()
{
for(int i = 0; i < 8; i++)
{
System.out.println("");
for(int j = 0; j < 8; j++)
{
System.out.print("[" + board[j][i] + "]");
}
}
}
}
Code:
public class KnightRunner
{
public static void main(String[] args)
{
int x = 0;
Knight mine = new Knight();
while(x < 64)
{
mine.getMoveLocations();
mine.selectMoveLocation();
mine.makeMove();
x++;
}
mine.printBoard();
}
}