Knight’s Tour C Source Code

22May/100

Knight's Tour is recursive and backtrackting algorithm that use brute force to find the solving.

#include "stdio.h"
#include "conio.h"

void printBoard(int**, int);
void clearBoard(int**, int);
void traceKnight(int**, int, int, int, int, int*);

int main(){
    int matrix;
    printf("Input Box Size : ");
    scanf("%d", &matrix);

    /* Board Matrix Building */
    int** board;
    board = (int**) malloc (sizeof(int)* matrix);
    for (int i = 0; i < matrix; i++)
    {
        board[i] = (int*) malloc (sizeof(int)* matrix);
    }

    /* Board Clearing Step */
    clearBoard(board, matrix);

    /* Knight Tracing Step */
    int checker = 0;
    traceKnight(board, matrix, 1, 0, 0, &checker);

    /* Printing the Result */
    printBoard(board,matrix);

    getch();
    return 0;
}

Main recursive function that trace and make the combination step of Knight

void traceKnight(int** board, int matrix, int step, int y, int x, int* checker)
{
    /* Step overboard */
    if (y < 0 || y > matrix-1 || x < 0 || x > matrix - 1)
    {
       return;
    }

    /* Board position has been taken */
    if (board[y][x] != 0)
    {
       return;
    }

    /* Take a step */
    board[y][x] = step;
    *checker = step;

    /* Choosing next step */
    traceKnight(board, matrix, step + 1, y - 2, x - 1, checker);
    traceKnight(board, matrix, step + 1, y - 2, x + 1, checker);
    traceKnight(board, matrix, step + 1, y - 1, x + 2, checker);
    traceKnight(board, matrix, step + 1, y + 1, x + 2, checker);
    traceKnight(board, matrix, step + 1, y + 2, x + 1, checker);
    traceKnight(board, matrix, step + 1, y + 2, x - 1, checker);
    traceKnight(board, matrix, step + 1, y + 1, x - 2, checker);
    traceKnight(board, matrix, step + 1, y - 1, x - 2, checker);

    /* Backtracking Step */
    if (*checker < matrix * matrix)
    {
       board[y][x] = 0;
    }
}

void clearBoard(int** board, int index)
{
    for (int y = 0; y < index; y++)
    {
        for (int x = 0; x < index; x++)
        {
              board[y][x] = 0;
        }
    }
}

void printBoard(int** board, int index)
{
    for (int y = 0; y < index; y++)
    {
        for (int x = 0; x < index; x++)
        {
              printf("%4d", board[y][x]);
        }
        printf("\n");
    }
}