This site is currently read-only as we are migrating to Oracle Forums for an improved community experience. You will not be able to initiate activity until January 31st, when you will be able to use this site as normal.

    Forum Stats

  • 3,890,899 Users
  • 2,269,649 Discussions
  • 7,916,821 Comments

Discussions

KnightsTour(heuristic solution)

dd9204a2-204e-43cf-9dcb-ac0566ad24eb
edited May 17, 2015 4:02PM in New To Java

can I ask for help?

i have a problem of converting this code into heuristic solution. I don't know what condition should I put to make heuristic solution works.This is just random move that will not complete the 64 tours.

    import java.util.Random;

   

    public class Knight

    {

    Random rand=new Random();

    public void start()

    {

    int[][] square = new int[8][8];

    int currentRow;

    int currentColumn;

    int x,y,count,count1=0;

    int moveNumber;

    int [] horizontal={2,1,-1,-2,-2,-1,1,2};

    int [] vertical={-1,-2,-2,-1,1,2,2,1};

  

  

    for(x=0;x<8;x++)

    {

    for(y=0;y<8;y++)

    {

    square[x][y]=0;

    }

    }

  

    currentRow=rand.nextInt(7);

    currentColumn=rand.nextInt(7);

    square[currentRow][currentColumn]=1;

  

    for(count=2;count<=64;count++)

    {

    for(moveNumber=0;moveNumber<8;moveNumber++)

    {

    currentRow+=vertical[moveNumber];

    currentColumn+=horizontal[moveNumber];

    if(currentColumn >= 0 && currentColumn < 8 && currentRow >= 0 && currentRow < 8 && square[currentRow][currentColumn]==0)

    {

    square[currentRow][currentColumn]=count;

    count1++;

    break;

    }

    else

    {

    currentRow-=vertical[moveNumber];

    currentColumn-=horizontal[moveNumber];

    }

    }

    }

  

    System.out.printf("The tour ended with %d moves\n \t0\t1\t2\t3\t4\t5\t6\t7\n",count1+1);

    for(x=0;x<8;x++)

    {

    System.out.printf("%d\t", x);

    for(y=0;y<8;y++)

    {

    System.out.printf("%d\t",square[x][y]);

    }

    System.out.println();

    }

    }

    }

    

If I were to use the heuristic solution,I need to add this code below but I have no clues how to continue changing it

    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 } };

Much appreciate for helping.

Answers

  • TPD-Opitz
    TPD-Opitz Dipl.-Ing, Dipl.-Inf GermanyMember Posts: 2,465 Silver Trophy
    edited May 17, 2015 4:02PM

    from here I found:

    An old heuristic which works very well for knight's tour(even on paper) is always jump to the MOST restricted square, that is a place where the knight has the least moves. 
    If there are more than one square with same restrictions then choose one of them at random.
    

    So what you have to do is to calculate the list of possible moves from the current field, remove the move that end at alredy used fields and for the rest lookup the "weight" of the target fields in the given array.

    bye

    TPD

This discussion has been closed.