Jump to content

User:Benhoman/Sandbox

From Wikipedia, the free encyclopedia
An animation of the Knight's Tour.
A graphical representation of the Knight's Tour implemented using Warnsdorff's Algorithm. The numbers in red circles denote the number of next possible moves that the knight could make if it moves from the start position to the one with the circle on it.

Warnsdorff's algorithm is a heuristic method for solving the Knight's Tour. The algorithm was first described in "Des Rösselsprungs einfachste und allgemeinste Lösung" by H. C. Warnsdorff in 1823.[1]

Overview

[edit]

Warnsdorff's rule was to always choose the next square that had the fewest possible further knight's moves. This more generally can be applied to any graph, by always choosing the next node that has smallest degree. Pohl generalized this by adding a rule for breaking ties. Although the Hamiltonian path problem is NP-hard in general, on many graphs that occur in practice this linear-time heuristic is able to successfully locate a solution.[2] The knight's tour is a special case.[3]

How it Works

[edit]

Warnsdorff’s algorithm for solving the Knight’s Tour problem works by placing the knight at any position on the board. The algorithm will then assess find the next possible moves it can take. From there the algorithm then calculates how many possible moves each of those next moves can make.[4] The algorithm then moves to the one that has the least amount of next possible moves and repeats the process again.[5][6]

What is the Knight’s Tour

[edit]

The Knight’s Tour is an ancient puzzle, where the goal is to move a knight to every position on a chess board without going to the same place twice. The Knight's Tour is a common problem in Computer Science classes that students must solve by creating an algorithm in a programming language. Warnsdorff's algorithm is only one option. An example of another answer to this problem would be a brute force attack algorithm, where the program will go from move to move until it either finds a working tour or it can't move anymore in which case the program will backtrack and tries a different path.

Pseudo code

[edit]

board variable which is a two dimensional array representing the chess board

main Function

moveNumber variable set equal to 2

temp variable array of two integers

move variable array of two integers

positionx variable for the x coordinate of the position

positiony variable for the y coordinate of the position

for every value of the variable i starting from zero ending at seven

for every value of the variable j starting from zero ending at seven

set board array at position i,j equal to zero to show that position hasn’t been reached yet

end for loop

end for loop

set board array at positionx,positiony equal to one for starting position

for every value of i from zero to sixty three

set move array at zero to positionx

set move array at one to positiony

call the getNetMoves function on the move array

set positionx to move array at zero

set positiony to move array at one

set board array at positionx,positiony to the moveNumber counter

increment moveNumber counter by one

end for

end Main function

getNextMoves takes move array as input

positionx variable to move array at zero

positiony variable to move array at one

accessibility variable set at eight for highest accessibility

check each possible move from positionx, positiony to see if its on the board

if the move is on the board and equal to zero

call getAccessibilty function to check the accessibility

if the returned value is less than the value of accessibility

set accessibility to the returned value

end if

end if

end getNextMoves function

getAccessibility takes x and y coordinates

set positionx variable to x

set positiony variable to y

create accessibility variable

if each of the next possible moves are on the board and equal to zero

increment the accessibility variable by one for each position that is possible and equal to zero

end if

end getAccessibility function

Example of the Knight’s Tour Problem Solved in C++

[edit]

The following code is an example of the source from a C++ file that will take an eight by eight chess board and solve the Knight’s Tour problem starting from a random position on the chess board.

<source lang="cpp">

  1. include <stdio.h>
  2. include <stdlib.h>
  3. include <time.h>

int checkMovability( int[][ 8 ], int, int ); void printBoard( int[][ 8 ] );


int main() {

   int currentRow = rand() % 8, currentColumn = rand() % 8, moveNumber, counter = 1;
   int vertical[ 8 ] = { -1, -2, -2, -1, 1, 2, 2, 1 }, horizontal[ 8 ] = { 2, 1, -1, -2, -2, -1, 1, 2 };
   int board[ 8 ][ 8 ] = { 0 };
   int tourLength[ 65 ] = { 0 };
   int tour, i;
   
   srand( time(NULL) );
   
   
   for (tour = 1; tour <= 1000; ++tour) {
       while ( checkMovability( board, currentRow, currentColumn ) == 1 && counter <= 64 ) {
           moveNumber = rand() % 8;
           
           if ( board[ currentRow + vertical[ moveNumber ] ][ currentColumn + horizontal[ moveNumber ] ] == 0 ) {
               //         printf("inner if 1\n");
               if ( ( currentRow + vertical[ moveNumber ] ) <= 7 && ( currentRow + vertical[ moveNumber ] ) >= 0 ) {
                   //            printf("inner if 2\n");
                   if ( (currentColumn + horizontal[ moveNumber ]) <= 7 && ( currentColumn + horizontal[ moveNumber ] ) >= 0 ) {
                       currentRow += vertical[ moveNumber ];
                       currentColumn += horizontal[ moveNumber ];
                       board[ currentRow ][ currentColumn ] = counter;
                       ++counter;
                       //               printBoard( board );
                       //               printf("Knight at %d %d\n", currentRow, currentColumn);
                   }
                   
               }
               
           }
       }
       
       //   printBoard( board );
       //   printf("No more moves can be made\n");
       ++tourLength[ counter - 1];
   }
   
   for (i = 0; i <= 64; ++i) {
       printf("%d: %d\n", i, tourLength[ i ] );
   }
   
   return 0;

}



int checkMovability( int grid[][ 8 ], int row, int column ) {

   int h[ 8 ] = { 2, 1, -1, -2, -2, -1, 1, 2 };
   int v[ 8 ] = { -1, -2, -2, -1, 1, 2, 2, 1 };
   int move;
   
   for (move = 0; move <= 7; ++move) {
       
       
       if ( grid[ row + v[ move ] ][ column + h[ move ] ] == 0 ) {
           if ( ( row + v[ move ] ) <= 7 && ( row + v[ move ] ) >= 0 ) {
               if ( (column + h[ move ]) <= 7 && ( column + h[ move ] ) >= 0 ) {
                   //               printf("checkMovability returned 1\n");
                   //               printf("checkMovability says you can move v: %d h: %d\n", v[ move ], h[ move ] );
                   //               printBoard( grid );
                   return 1;
               }
           }
       }
   }
   
   return 0;

}




void printBoard( int grid[][ 8 ] ) {

   int i, j;
   
   printf("\n\n");
   
   for (i = 0; i <= 7; i++) {
       for (j = 0; j <= 7; j++) {
           printf("%4d", grid[ i ][ j ] );
           if ( (j + 1) % 8 == 0 )
               printf("\n\n");
       }
   }
   
   return;

}

References

[edit]
  1. ^ Alwan, Karla (1992), "Finding Re-entrant Knight's Tours on N-by-M Boards", ACM Southeast Regional Conference, New York, New York: ACM, pp. 377–382 {{citation}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
  2. ^ Pohl, Ira (July 1967). "A method for finding Hamilton paths and Knight's tours". Communications of the ACM. 10 (7): 446–449. doi:10.1145/363427.363463.
  3. ^ Alwan, Karla (1992), "Finding Re-entrant Knight's Tours on N-by-M Boards", ACM Southeast Regional Conference, New York, New York: ACM, pp. 377–382 {{citation}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
  4. ^ Törnberg, Gunno (1999). "Warnsdorff's rule". Retrieved 2008-9-25. {{cite web}}: Check date values in: |accessdate= (help)
  5. ^ Alwan, Karla (1992), "Finding Re-entrant Knight's Tours on N-by-M Boards", ACM Southeast Regional Conference, New York, New York: ACM, pp. 377–382 {{citation}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
  6. ^ Cancela, Hector (2006-08-31). "Counting Knight's Tours through the Randomized Warnsdorff Rule". {{cite journal}}: Cite journal requires |journal= (help); Unknown parameter |coauthors= ignored (|author= suggested) (help)
[edit]