#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 8

int main() {
    int horizontal[8] = {2, 1, -1, -2, -2, -1, 1, 2};
    int vertical[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
    int tourLengths[65] = {0};
    
    srand(time(NULL));

    for (int tour = 0; tour < 1000; tour++) {
        int board[SIZE][SIZE] = {0};
        int currentRow = rand() % 8;
        int currentCol = rand() % 8;
        board[currentRow][currentCol] = 1;
        int moveNumber = 1;
        int canMove = 1;

        while (canMove) {
            int validMoves[8] = {0};
            int numValidMoves = 0;

            for (int moveType = 0; moveType < 8; moveType++) {
                int testRow = currentRow + vertical[moveType];
                int testCol = currentCol + horizontal[moveType];

                if (testRow >= 0 && testRow < SIZE && testCol >= 0 && testCol < SIZE) {
                    if (board[testRow][testCol] == 0) {
                        validMoves[numValidMoves] = moveType;
                        numValidMoves++;
                    }
                }
            }

            if (numValidMoves > 0) {
                int moveType = validMoves[rand() % numValidMoves];
                currentRow += vertical[moveType];
                currentCol += horizontal[moveType];
                moveNumber++;
                board[currentRow][currentCol] = moveNumber;
            } else {
                canMove = 0;
            }
        }
        tourLengths[moveNumber]++;
    }

    printf("Tour Length\tFrequency\n");
    for (int i = 1; i <= 64; i++) {
        if (tourLengths[i] > 0) {
            printf("%d\t\t%d\n", i, tourLengths[i]);
        }
    }

    return 0;
}