Knight's Tour Problem 2

Hi,

THis time i only have one question to get clear of so far. Now my book tells me to develop a strategy to move the knight. Each square on the board is labelled with accessibility numbers which tells how hard are they accessed. They are as follows on a 8x8 chess board:

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

Here is the bit i don't understand:
---------------------------------------------------------------------------------
'Now write a version of the Knight's Tour program using the accessibility heuristic. At any time, the knight should move to the square with the lowest accessibiloity number. In case of a tie, the knight may move to any of the tied squares. Therefore, the tour may begin in any of the four corners. (Note: As the knight moves around the chess board, your program should reduce the acessibility numbers as more and more squares become occupied. In this way, at any give time during the tour, each available square's accessbility number will remain equal to precisely the number of squares from which that square may be reached.) '
----------------------------------------------------------------------------------

WHat IS a tie?

How do i reduce the accessibility numbers ? Each time the knight moves reduce one from all squares? This can't make sense.

Pls help.

thnx

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.

To determine which cell has the lowest accessibility, do i have to use some sort of sorting algorithm such as bubble sort ?

and for each move i have to calculate how many squares are accessible from that square, do that for every move, will it slow down the program a little bit ? Like because i have to use a for loop of a while loop ?

thnx

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.

Quote:

---

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

---

Each time, i have to compare 8 (max) accessiblity numbers, how can i simple use the if statement ?

OK maybe this will clear things up a little bit, here is my current code:

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 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 i, j;

  while ( end != 1 ) {
      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 ) {
            board[ currentRow ][ currentCol ] = 1;
            currentRow += vertical[ moveNumber ];
            currentCol += horizontal[ moveNumber ];
            ++totalMoves;
            printf( "board[ %d ][ %d ]\n", currentRow, currentCol );
            break;
        }
        else { /* Next move not possible */
            if ( moveNumber == 7 )
              end = 1;            /* No more possible moves... */
            continue;
        }
      }
  }

  return totalMoves;
}

---

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;

}

---

anyone, pls give a hand. The code will only generate two moves, although that two moves doesn't move according to the accessibility numbers...

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.

thnx i will givit a try.

Here is the code that I wrote which
shows the problem with the code that you
wrote. Your method won't work as the knight
will get stuck after a certain number of moves.
This one will run until it gets stuck after 59
moves.

At the ending sequence the board looks like


11111111
11111111
11111111
11111111
11111011
11100011
11111111
11111111

Using (row, col)
(0, 0) Is the top left corner and the knight is at (5, 2)
The knight as no where to go except for a used square.

worked appreciate it nick. Need any software just ask me.