Thread: Knight's Tour Problem 2

Let's say your knight starts in the top left corner, which I refer to as (0,0).

From that place, we have two places to which we can move, either (1, 2), or (2, 1). The accessability of each of these cells is 6, so we have a tie. According to the rules of the problem, we may choose either of the squares. Let's say that we choose (1, 2)

Also, since we've visited cell (0,0), it is no longer accessable, therefore that's one less cell that (1, 2) has access to, and one less cell that (2, 1) has access to. Therefore, when we mark cell (0, 0) as unaccesable, we also have to reduce the accessability of (1, 2) and (2, 1) to 5. It doesn't matter if we do this before or after choosing which cell to jump to.

Now we are at cell (1, 2). Here's a listing of the 5 cells we can access from here....
(0, 4) Accessability 4
(2, 0) Accessability 4
(2, 4) Accessability 6
(3, 1) Accessability 6
(3, 3) Accessability 8

Now we have another tie. So, according to the rules, we may choose either (0, 4), or (2, 0). Also, since cell (1, 2) has been visited, all the cells which have access to (1, 2) will have their accesability reduced by one (clearly, these are the same points as those which we could access from (1, 2)).

And I take it that we just repeat this untill we've nowhere else to move.

do i have to use some sort of sorting algorithm
you don't have to sort anything.. just compare each value...

Code:

if(accessibility[x] < accessibility[y])
{
  // use X
}
else
{
  // use Y
}

for each move i have to calculate how many squares are accessible from that square

well, each place you can access is 2 squares one way, and one in the other.

ie:
x - 2, y - 1
x - 2, y + 1
x + 2, y - 1
x + 2, y + 1
x - 1, y - 2
x - 1, y + 2
x + 1, y - 2
x + 1, y + 2

you can put a loop in if you want... but it might not be worth it... just make sure that each of those combinations is inside the square.. and that the acessibility of a particular square is not zero.

good luck
U.

That's what i have so far. It doesn't work, it only display 2 moves, but it does choose the lowest accessibility number to go to for that two moves. I would like to know why it won't go further as it should. What's wrong with the code and where ?

thnx in advance.

Code:

/* Knight's Tour ( recursive version ) */

#include <stdio.h>

/* 'col' = column */

int knights_tour( int startingRow, int startingCol, int board[][ 8 ] ); /* returns the number of moves made */

int out_of_bounds( int nextRow, int nextCol ); /* check if next move is off the board */

int visited( int nextRow, int nextCol, int board[][ 8 ] );       /* check if next square is visited already */

int bubbleSort( int a[] );

int main()
{
   int board[ 8 ][ 8 ] = { 0 };

   printf( "***Knight's Tour***\n\n" );

   printf( "\nNumber of moves made: %d \n\n", knights_tour( 0, 0, board));

   getch();

   return 0;
}

int out_of_bounds( int nextRow, int nextCol )
{
   /* Returns 1 if out of bounds.
      Returns 0 if O.K.          */

   if ( nextRow < 0 || nextRow > 7 )
      return 1;

   if ( nextCol < 0 || nextCol > 7 )
      return 1;

   /* O.K. */
   return 0;
}

int visited( int nextRow, int nextCol, int board[][ 8 ] )
{
   /* Returns 1 if visited.
      Returns 0 if not visited. */

   if ( board[ nextRow ][ nextCol ] == 1 )
      return 1;

   return 0;
}

int knights_tour( int startingRow, int startingCol, int board[][ 8 ] )
{
       /* moveNumbers:     0  1   2   3   4   5  6  7 */
   int horizontal[ 8 ] = { 2, 1, -1, -2, -2, -1, 1, 2 };
   int vertical[ 8 ]   = { -1, -2, -2, -1, 1, 2, 2, 1 };
   int temp1, temp2;
   int currentRow = startingRow;
   int currentCol = startingCol;
   int totalMoves = 0;
   int end = 0;
   int moveNumber;
   int arrayToSort[ 8 ] = { 0 };
   int retval;
   int i;
   int potentialMoves;
   int access[ 8 ][ 8 ] = { { 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 } };

   while ( end != 1 ) {
      potentialMoves = 0; /* reset number of potential moves */

      for ( moveNumber = 0; moveNumber <= 7; moveNumber++ ) {
         temp1 = currentRow + vertical[ moveNumber ];
         temp2 = currentCol + horizontal[ moveNumber ];
         if ( out_of_bounds( temp1, temp2 ) != 1 && visited( temp1, temp2, board ) != 1 ) {
            arrayToSort[ moveNumber ] = access[ temp1 ][ temp2 ];
            ++potentialMoves;
         }
         else { /* Next move not possible */
            if ( moveNumber == 7 )
               end = 1;             /* No more possible moves... */
            continue;
         }
      }

      access[ currentRow ][ currentCol ] = potentialMoves; /* reduce accessibility number */

      retval = bubbleSort( arrayToSort );  /* returns smallest accessibility number */

      for ( moveNumber = 0; moveNumber < 8; moveNumber++ ) {
         temp1 = currentRow + vertical[ moveNumber ];
         temp2 = currentCol + horizontal[ moveNumber ];
         if ( access[ temp1 ][ temp2 ] == retval ) {
            board[ currentRow ][ currentCol ] = 1;
            currentRow += vertical[ moveNumber ];
            currentCol += horizontal[ moveNumber ];
            ++totalMoves;
            printf( "board[ %d ][ %d ]\n", currentRow, currentCol );
            printf( "%d\n", retval );

            break;
         }
      }

   }
   return totalMoves;
}

int bubbleSort( int a[] )
{
   /* ascending sort */

   int pass, i, j, hold, arraySize = 8;

   for ( pass = 1; pass <= arraySize - 1; pass++ )
      for ( j = 0; j <= arraySize - 2; j++ )
         if ( a[ j ] > a[ j + 1 ] ) {
            hold = a[ j ];
            a[ j ] = a[ j + 1 ];
            a[ j + 1 ] = hold;
         }

   /* reusing j */
   for ( j = 0; j < 8; j++ )
      if ( a[ j ] != 0 )
         return a[ j ];
      else
         continue;

}

I'm sorry, but the problem with that code is not a couple bugs, the code itself is incorrect enough that I'm not sure it can be 'fixed'.

You need to work with 3 seperate steps...

Step one: choose the X and Y such that they have the lowest accessability from the current square.
Step two: mark the current square as visited.
Step three: decrease the accessability of all the squares which can access the current square by one.

For step one, you don't need to sort. You should be using a for loop that has the following code...

Code:

     if (accessability[tempX][tempY] < 
         accessability[move2MeX][move2MeY]);
     {
      move2MeX = tempX;
      move2MeY = tempY;
     }

This little snippet of code will compare the accessability of square tempX, tempY with that of move2MeX, move2MeY, and if the accessability of temp is less than that of move2Me, then it will replace move2Me with temp. By doing this for every square you want to compare, in the end, move2Me be the square with the lowest accessability.

For step two, I suggest that you only use one array to represent the board, use your access array. If a square has been visited, then mark the square as having an access of 0 or -1.

Step three is just a simple for loop.