Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 2 of 2
  1. #1
    New to the CF scene
    Join Date
    Dec 2009
    Location
    Washington
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Question Knight's Tour Project - fully coded, but bad output

    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 don't want to plagiarize). 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]
    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.

    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] + "]");
    #             }
    #         }
    #     }
    # }
    And, here's my tester file:

    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();
    #     }
    #  
    # }
    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!

  • #2
    Regular Coder
    Join Date
    Apr 2005
    Location
    Ohio
    Posts
    254
    Thanks
    1
    Thanked 63 Times in 63 Posts
    Don't have time to go through your code right now but do print your board after each move within your main method. This will tell you whether you're somehow overwriting squares or going off the board and hopefully give you an idea of where the problem lies.


  •  

    Tags for this Thread

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •