Friday, March 29, 2024
HomeC ProgrammingSetting Up the Knight’s Tour

Setting Up the Knight’s Tour



I first learn in regards to the Knight’s Tour once I was a child. My mother purchased the Time Life collection of books on computer systems. It it, the Knight’s Tour program is offered, which fascinated me. In any case this time, I lastly got down to code the tour myself.

The aim of the knight’s tour is to maneuver a knight round a chessboard in a sample the place the knight by no means visits the identical sq. twice. You may learn up on the main points on the all-knowing Wikipedia.

To me, it appeared apparent that coding the knight’s tour includes some form of recursion. When the knight can now not transfer, it should be backed out and check out a special path. However based on the mathematicians who research these items, equivalent to an method would possibly take a painfully very long time to finish.

To be expedient, I opted to make use of Warnsdorff’s rule. (See the Wikipedia article.) This heuristic states that the knight ought to transfer to the sq. that has the fewest variety of subsequent strikes.

For instance, in Determine 1, the knight is in row three, column seven. It has six potential strikes: Two of them have eight subsequent strikes, two have 4, one has six, and one legitimate transfer has solely two subsequent strikes. (Technically that final location has just one subsequent transfer because the knight shouldn’t transfer again to its beginning sq. – however first issues first!)

Knight on a chessboard with potential moves

Determine 1. The knight at a random place, its six legitimate strikes, and rely of subsequent strikes.

In keeping with Warnsdorff’s rule, the knight ought to transfer to the primary row, eighth column, the place it has solely two (one) legitimate subsequent strikes. This course of continues, mapping out the knight’s tour across the chessboard. Earlier than implementing this answer, I have to replace the code from final week’s Lesson so as to add a ahead transfer rely forecast. This enchancment includes adjustments to the foremost() and chess_board() capabilities.

To replace the foremost() perform, two new arrays are added: subsequent[] and tally[].

The subsequent[] array holds the knight’s subsequent collection of strikes from potential new areas.

The tally[] array holds the transfer rely for every of the following, subsequent strikes.

Right here is the up to date foremost() perform:



int foremost()
{
    int knight,x;
    int strikes[KM],subsequent[KM],tally[KM];

    
    srand( (unsigned)time(NULL) );

    
    knight = rand() % (SIZE*SIZE);

    
    moveto(knight,strikes);

    
    for( x=0; x<KM; x++ )
    {
        
        if( strikes[x] != -1 )
        {
            moveto(strikes[x],subsequent);
            tally[x] = movecount(subsequent);
        }
        else
        {
            
            tally[x] = strikes[x];
        }
    }

    
    chess_board(knight,strikes,tally);

    return(0);
}

A for loop processes all potential strikes obtained from the moveto(knight,strikes); name. For every legitimate location within the strikes[] array, the knight is pretend-relocated to the given place. A second name is made to moveto() to search out the following strikes from the brand new sq.. These are saved within the subsequent[] array. Then the tally[] array is full of outcomes from the movecount() perform.

The chess_board() perform is up to date to output the movecount() values saved within the tally[] array. The output seems as proven in Determine 1.

You may view the entire code on GitHub, together with my feedback that designate numerous particulars.

At this level, the code is getting advanced! It’s severe mind work to maintain monitor of all of the items. But, if I wish to implement the Knight’s Tour utilizing Warnsdorff’s rule, these particulars are crucial.

In subsequent week’s Lesson I full the Knight’s Tour code with some main updates and modifications.

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments