knight's tour problem

Hi

I've made an application that simulates knight's moves on a chessboard
the program takes a specific move of the eight possible moves and applies it by setting the appropriate element in the array board to 1 which already means that this square has been visited.
I also created an array accessibility that determines the accessibility of each square, for example the four corner squares have the accessibility value of 2 because there are only two squares that can be reached from each square of the four corner squares.

I am aiming now to improve this application and make it able to make decisions and make moves toward the lowest accessibility squares so that I've to make a tour with the knight that consists of 64 moves and the knight must land of each square on the board only once.

but actually I don't know how to do this. so I'll be thankful if there are more hints.

my code (I've the main method in a separate class):

Code:

---

public class Chessboard {

        public int currentRow = 0;
        public int currentCol = 0;
        private int[][] board = new int[8][8];
        private int[] horizontal = new int[8];
        private int[] vertical = new int[8];
        public int totalMoves = 0;
        private int[][] accessibility = new int[8][8];

        //constructor
        public Chessboard () {
                // initialize board
                for (int row = 0; row < board.length; row++) {
                        for (int col = 0; col < board[row].length; col++) {
                                board[row][col] = 0;
                        }// end nested for
                }// end for
               
                board[currentRow][currentCol] = 1;
                       
                // initialize moves
                horizontal[ 0 ] = 2;
                vertical[ 0 ] = -1;
               
                horizontal[ 1 ] = 1;
                vertical[ 1 ] = -2;
               
                horizontal[ 2 ] = -1;
                vertical[ 2 ] = -2;
               
                horizontal[ 3 ] = -2;
                vertical[ 3 ] = -1;
               
                horizontal[ 4 ] = -2;
                vertical[ 4 ] = 1;
               
                horizontal[ 5 ] = -1;
                vertical[ 5 ] = 2;
               
                horizontal[ 6 ] = 1;
                vertical[ 6 ] = 2;
               
                horizontal[ 7 ] = 2;
                vertical[ 7 ] = 1;
               
                //initializing accessibility
                                for (int row = 2; row <= 5; row++) {
                                        for (int col = 2; col <= 5; col++) {
                                                accessibility[row][col] = 8;
                                        }
                                }
                               
                                for (int col = 2; col <= 5; col++) {
                                        accessibility[1][col] = 6;
                                        accessibility[6][col] = 6;
                                        accessibility[0][col] = 4;
                                        accessibility[7][col] = 4;
                                }
                               
                                for (int row = 2; row <= 5; row++) {
                                        accessibility[row][0] = 4;
                                        accessibility[row][7] = 4;
                                        accessibility[row][1] = 6;
                                        accessibility[row][6] = 6;
                                }
                               
                                accessibility[0][0] = 2;
                                accessibility[0][7] = 2;
                                accessibility[7][0] = 2;
                                accessibility[7][7] = 2;
                       
                                accessibility[0][1] = 3;
                                accessibility[0][6] = 3;
                                accessibility[1][0] = 3;
                                accessibility[1][7] = 3;
                                accessibility[6][0] = 3;
                                accessibility[6][7] = 3;
                                accessibility[7][1] = 3;
                                accessibility[7][6] = 3;
                               
                                accessibility[1][1] = 4;
                                accessibility[1][6] = 4;
                                accessibility[6][1] = 4;
                                accessibility[6][6] = 4;
               
        }// end constructor
       
       
       
        public void makeMove (int moveNumber) {

                currentCol += horizontal[moveNumber];
                currentRow += vertical[moveNumber];
               
                if ((currentRow > 7 || currentCol > 7) || (currentCol < 0) || (currentRow <0) ) {
                        //prevent landing out
                        currentCol -= horizontal[moveNumber];
                        currentRow -= vertical[moveNumber];
                }
                else {
                       
                        if (board[currentRow][currentCol] == 0) {
                                board[currentRow][currentCol] = 1;
                                totalMoves++;
                                accessibility[currentRow][currentCol] = 9;
                        }
                        else {
                                //prevent visiting the place more than once
                                currentCol -= horizontal[moveNumber];
                                currentRow -= vertical[moveNumber];
                        }
                }
               
        }// end makeMove
       
        public void displayBoard () {
               
                for (int row = 0; row < board.length; row++) {
                        for (int col = 0; col < board[row].length; col++) {
                                System.out.printf("pos[%d][%d] = %d\n", row, col, board[row][col]);
                        }// end nested for
                }// end for
        }// end displayBoard
}

---

Are you just trying to move through the board once and only once? Then want a list of the moves it performed to get there?
I might suggest a stack for this, but based on the current setup, you'll need an array that can hold your 64 locations and an array keeping track of the last move made from each location.
This is a brute-force method, but would work like this:

Start somewhere, mark it visited. start your list with that place
count = 0
while not done:
If N-N-E available and not visited and not N-N-E from here before (separate array/list)
mark moved[HERE] = N-N-E
move N-N-E
mark new current visited, add to list of moves
count ++
Else If N-N-W available .....

...

Else if S-S-W (OR LAST IN CHOICE OF MOVES) not available
count --
BACK UP

...

if count == 63 done = true!

I tried a similar way by performing the eight possible moves and checking whether the location is available or not if available I mark it as not available and try another location
if not i stay at the same place and try different move. but my problem is to make the knight make a decision to move toward the square that has the lowest accessibility(has the least number of squares around it that can be reached only from it). I don't know how to do this for sorry.

Quote:

---

Originally Posted by Kareem Mesbah

I tried a similar way by performing the eight possible moves and checking whether the location is available or not if available I mark it as not available and try another location
if not i stay at the same place and try different move. but my problem is to make the knight make a decision to move toward the square that has the lowest accessibility(has the least number of squares around it that can be reached only from it). I don't know how to do this for sorry.

---

That's the 'Warnsdorff's rule' for a night tour; it solves the entire tour in linear time and you never have to back track.

kind regards,

Jos

Quote:

---

Originally Posted by JosAH

That's the 'Warnsdorff's rule' for a night tour; it solves the entire tour in linear time and you never have to back track.

kind regards,

Jos

---

thank you very much :)