Develop a program in which the knight moves around an empty chessboard and touch

Question

Develop a program in which the knight moves around an empty chessboard and touches each of the 64 squares only once. The board should be represented by a an 8 by 8 double-scripted array board, with each square initialized to zero.

The eight moves a knight can make, as shown in the image, can be described by two single-subscripted arrays:

horizontal[ 0 ] = 2
horizontal[ 1 ] = 1
horizontal[ 2 ] = -1
horizontal[ 3 ] = -2
horizontal[ 4 ] = -2
horizontal[ 5 ] = -1
horizontal[ 6 ] = 1
horizontal[ 7 ] = 2

vertical[ 0 ] = -1
vertical[ 1 ] = -2
vertical[ 2 ] = -2
vertical[ 3 ] = -1
vertical[ 4 ] = 1
vertical[ 5 ] = 2
vertical[ 6 ] = 2
vertical[ 7 ] = 1

Let the variables currentRow and currentColumn indicate the row and column of the knight's current position on the board. To make a move of type moveNumber, where moveNumber is between 1 and 7, your program uses the statements:

currentRow += vertical[ moveNumber ];

currentColumn += horizontal[ moveNumber ];

Keep a counter that varies from 1 to 64. Record the latest count in each square the knight moves to. Remember to test each potential move to see if the knight has already visited the square.

Please only use <stdio.h>, <stdlib.h>, <math.h>, and <time.h>. We haven't learned any other headers. You can also use #define statements.

Explanation / Answer

There are two ways you could try to solve this problem. You could write a program that simply "walks through" all of the possibilities until it finds a successful sequence. This would be considered a "brute force" method. You could also try to mathematically come up with some sort of derivation or algorithm that simplifies or eliminates certain possibilites to reduce the complexity.

Since you didn't make any mention of having to derive anything, I used the brute force method in my code. While it requires a lot of number crunching and depending on processor speed can take some time to arrive at an answer, it is also the most straight forward. The "trick" became figuring out a way to have the program do millions of iterations without having to write a rediculously long and complex code. This is where the idea of a "recursive function" became useful. Basically, a recursive function is one that within the function you actually make a "call" to the function...sort of a function within a function. I suggest you do some more research on recursive functions and how they work and how they can be extremely useful.

In my program, I created a function called "moveKnight" that was responsible for doing all of the sequencing and testing. Within this function, there are several calls to this same function. I suggest you take a look at my code and comments, and try to understand the software flow for yourself. And feel free to ask any questions about something you don't understand.

In the "main" of the program, I simply made a call to the moveKnight function in order to find a suitable sequence, and then I printed out the information in two forms. The first shows each step and the corresponding position on the board (matrix style). The second actually "draws" the chess board and physically shows the order of moves. The redundancy isn't neccessary, but they did help me to troubleshoot and debug.   

One other note: You can change the starting position of the knight in the "main," but be aware that doing so can affect the computation time (since we're using the brute force method...it just depends on how fast the computer can find a correct sequence and changing the initial conditions changes the "test pattern.")

As it's set right now at (0,0), it takes my computer about 4 seconds to come up with the answer. Changing it could result in shorter times, or extremely longer times. Feel free to play with it.

Below is the code. Please try to go through and thoroughly understand everything. Let me know if you have any questions.

#include "stdlib.h"
#include "stdio.h"

int horizontal[8] = {2,1,-1,-2,-2,-1,1,2}; //Define possible knight movements
int vertical[8] = {-1,-2,-2,-1,1,2,2,1};

int sequence[64][2] = {0,0}; //Array to store the successful sequence of moves

int board[8][8] = {0,0}; //Initialize all board spaces to zero


int moveKnight(int currentRow, int currentColumn, int counter)
{
    int success;
    int moveNumber;

    for(moveNumber = 0; moveNumber < 8; moveNumber++)
    {
        currentRow += vertical[moveNumber];       //Move piece to new spot
        currentColumn += horizontal[moveNumber];

        if(7 >= currentRow && currentRow >= 0 && 7 >= currentColumn && currentColumn >= 0) //Check if knight is on board
        {
            if (board[currentRow][currentColumn] == 0)        //Check if space has been occupied already
            {
                board[currentRow][currentColumn] = counter; //Record count to space
                sequence[counter - 1][0] = currentRow;        //Store move in sequence
                sequence[counter - 1][1] = currentColumn;

                if (counter == 64)    //Check to see if we've reached the last open space
                {
                    return 1;   //Success...an answer has been found
                }

                success = moveKnight(currentRow, currentColumn, counter + 1); //Find the next move
                if (success == 1)
                {
                    return 1; //Sucess...an answer has been found
                }

                board[currentRow][currentColumn] = 0; //Answer not found, reset space to unvisited
                currentRow -= vertical[moveNumber];         //Move piece back
                currentColumn -= horizontal[moveNumber];
            }
            else
            {
                currentRow -= vertical[moveNumber];         //Move piece back
                currentColumn -= horizontal[moveNumber];
            }
        }
        else
        {
                currentRow -= vertical[moveNumber];         //Move piece back
                currentColumn -= horizontal[moveNumber];
        }
    }
    return 0; //Failure
}


main()
{
    int startRow = 0;
    int startColumn = 0;
    int counter = 1;
    int i;

    int row, column;

    int success; //Flag to determine if a solution has been found

    board[startRow][startColumn] = counter;       //Record count '1' to initial space
    sequence[0][0] = startRow;        //Store initial position in sequence
    sequence[0][1] = startColumn;

    success = moveKnight(startRow, startColumn, 2);

    if (success == 1)
    {

        printf("Answer found ");
        printf("Move Row Column ");
        for(i = 0; i < 64; i++)
        {
            printf("%d %d %d ", i + 1, sequence[i][0], sequence[i][1]);
        }

        printf(" ");

        for(row = 0; row < 8; row++)
        {
            for(column = 0; column < 8; column++)
            {
                printf("%d ", board[row][column]);
            }
            printf(" ");
        }

    }
    else
    {
        printf("Answer not found");
    }

    exit(0);
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.