There are many classic examples of a knights tour in JAVA. A tipsy/drunk knights

Question

There are many classic examples of a knights tour in JAVA. A tipsy/drunk knights tour uses a similar algorithm to try to visit every space from a 8X8 grid. What makes him tipsy is the process of using random to achieve the task. The aim is a sequence of 63 consecutive legal knight moves which the knight visits each of the board spaces on an 8 by 8 grid exactly once. Please use THIS method NOT backtracking or any other algorithm to write a java code for the tipsy knight.. Use a random starting square from the board to make a sequence of the knights moves. Do this by selecting the knights next move randomly from the list of available/legal moves from the current square to a square not yet visited!! The tour ends when there are no more moves legally available from the current position of the knight. Once the algorithm is working we must do it several times and display the best tour. A tour is better than the other if it makes it to more squares (ex: a tour that lasts 40 moves is better than one that lasts 5). We must display the best tour of several hundred runs. Displaying a tour means output a 8x8 table or grid which shows the tour using consecutive integers (1,2,3,4,5....J which represents the sequence of the tour. Display the first five tours that are generated by this method. We want to keep a record of the longest tour created and display a tour only if it longer than the current longest tour so far. The best tour means the one that gets closest to getting to every single square on the board. The program can generate 1000+ tours and display a result after every 100 tours to make sure the program is still functioning

Explanation / Answer

import java.util.*;
import java.io.*;

public class Lab16ast
{
    public static void main (String args[]) throws IOException
    {
        Knight knight = new Knight();
        knight.getStart();
        knight.solveTour();
        knight.displayBoard();
    }
}

class Knight {
    private int board[][];
    private int startRow;
    private int startCol;
    private int rowPos;
    private int colPos;
    private int moves;
    //Matrix of possible moves
    private int movesOption[][] = {
        {-2,1},
        {-1,2},
        {1,2},
        {2,1},
        {2,-1},
        {1,-2},
        {-1,-2},
        {-2,-1}
    };
    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}
};

    public Knight() {}

    public void getStart() throws IOException{
            Scanner input = new Scanner(System.in);
  
            System.out.print("Enter starting row: ");
            startRow = input.nextInt() - 1;
  
            System.out.print("enter starting col: ");
            startCol = input.nextInt() - 1;
  
            System.out.println();
    }

    public void displayBoard() {
        System.out.println();
        for (int y = 0; y < board.length; y++) {
            for (int x = 0; x < board[y].length; x++)
                    System.out.printf("%02d ",board[y][x]);
            System.out.println();
        }
        System.out.println(" The knight made " + moves + " moves");
    }

    private boolean getMove()
    {
        int moveID = -1;
        int numOfmove = 8;
        //go through each option in movesOption until one works.
        for (int x = 0; x < movesOption.length; x++) {
            if (rowPos + movesOption[x][0] >= 0 && rowPos + movesOption[x][0] < board.length) {
                if (colPos + movesOption[x][1] >= 0 && colPos + movesOption[x][1] < board[0].length) {
                    if (board[rowPos + movesOption[x][0]][colPos+movesOption[x][1]] == 0) {
                        if (ACCESS[rowPos + movesOption[x][0] + 2][colPos + movesOption[x][1] + 2] <= numOfmove) {
                            numOfmove = ACCESS[rowPos + movesOption[x][0] + 2][colPos + movesOption[x][1] + 2];
                            moveID = x;
                        }
                    }
                }
            }
    }

        if (moveID != -1) {
            board[rowPos+=movesOption[moveID][0]][colPos+=movesOption[moveID][1]] = ++moves;
            return true;
        }
        return false;
    }

    public void solveTour()
    {
        while (moves != 64)
        {
            moves = 0;
      
                board = new int[8][8];
      
                rowPos = startRow;
                colPos = startCol;
      
                board[rowPos][colPos] = ++moves;
      
                Random rnd = new Random();
      
                for (int s = movesOption.length - 1; s > 0; s--) {
                    int index = rnd.nextInt(s + 1);
                    int temp[] = movesOption[index].clone();
                    movesOption[index] = movesOption[s];
                    movesOption[s] = temp.clone();
                }
        while(getMove());
        }
        }
        }

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.