Saludos, tengo un programa que dado un tamaño n de un tablero, me diga cual es el numero maximo de caballos que se pueden colocar en ese tablero sin atacarse? y de cuantas formas, el programa me tiene que dar maximo 10 soluciones solamente.

e hice un codigo que me pida una (x,y) aleatoria para poner en esa casilla al caballo y despues calcular los 8 movimientos posibles y asegurarme que no haya otra pieza en ninguna de esas 8 casillas que marque, para que no se ataquen,en caso de que si haya otro caballo que pueda atacar pedir otra (x,y) aleatoria, y asi sucesivamente hasta que tengo el total de caballos en el tablero, como son 10 tableros maximo, a cada uno le saco el numero total de caballos y esos totales los almaceno en un arreglo para despues buscar con una funcion el mayor de ellos. y ese seria mi maximo. Pero el problema es que ese no es el maximo, porque solo son 10 tableros, pero por ejemplo si fueran 20 tableros a los que les calculo su total de caballos puede ser que en alguno de esos haya un numero de caballos mayor que al mayor que calcule de los 10 tableros que tenia

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define NO_CASILLAS_DISPONIBLES 0
#define MAX_SOLUCIONES 10
 
void inicializarTablero(char **tablero,int n);
int insertarCaballos(char **tablero,int fila,int columna,int casillasDisponibles,int numCaballos,int n);
int verificarMovimientos(char **tablero,int fila,int columna,int casillasDisponibles,int n);
void imprimirTablero(char **tablero,int n);
int maximoCaballos(int totalCaballos[]);
 
int main()
{
    FILE *fd;
    int n,i,j = 0,fila,columna,numCaballos,totalCaballos[MAX_SOLUCIONES],casillasDisponibles,MaxCaballos;
    char **tablero;
    do
    {
        printf("Dame tamanio de tablero: ");
        scanf("%d",&n);
    }while(n < 2 || n > 20);/*
    if((fd = fopen("caballos_xx.txt","w"))!=NULL)
    {*/
        srand(time(NULL));
        tablero = malloc(n*sizeof(char*));
        for(i = 0;i < n;i++)
           tablero[i] = malloc(n);
        while(j < MAX_SOLUCIONES)
        {
            numCaballos = 0;
            casillasDisponibles = n*n;
            fila = rand() % n;
            columna = rand() % n;
            printf("(%d,%d)\n",fila,columna);
            inicializarTablero(tablero,n);
            totalCaballos[j] = insertarCaballos(tablero,fila,columna,casillasDisponibles,numCaballos,n);
            imprimirTablero(tablero,n);
            printf("\n\nEl numero maximo de caballos en esta solucion es de %d\n",totalCaballos[j]);
            j++;
        }
        MaxCaballos = maximoCaballos(totalCaballos);
        printf("\nEl numero maximo de caballos en un tablero de %d x %d sin atacarse es %d\n",n,n,MaxCaballos);/*
    }
    else
       printf("No se pudo crear archivo");*/
    return 0;
}
 
void inicializarTablero(char **tablero,int n)
{
    int i,j;
    for(i = 0;i < n;i++)
    {
        for(j = 0;j < n;j++)
           tablero[i][j] = '0';
    }
}
 
int insertarCaballos(char **tablero,int fila,int columna,int casillasDisponibles,int numCaballos,int n)
{
    if(casillasDisponibles > NO_CASILLAS_DISPONIBLES)
    {
        if(tablero[fila][columna] == '0')
        {
            tablero[fila][columna] = 'C';
            casillasDisponibles = verificarMovimientos(tablero,fila,columna,casillasDisponibles,n);
            numCaballos++;
            fila = rand() % n;
            columna = rand() %n;
            insertarCaballos(tablero,fila,columna,casillasDisponibles,numCaballos,n);
        }
        else
        {
            fila = rand() % n;
            columna = rand() %n;
            insertarCaballos(tablero,fila,columna,casillasDisponibles,numCaballos,n);
        }
    }
    else
       return numCaballos;
}
 
int verificarMovimientos(char **tablero,int fila,int columna,int casillasDisponibles,int n)
{
    int i,j,nuevaFila,nuevaColumna,eliminadas;
    eliminadas = casillasDisponibles-1;
    nuevaFila = fila + 2;
    nuevaColumna = columna -1;
    if((nuevaFila>=0&&nuevaFila<n)&&(nuevaColumna>=0&&nuevaColumna<n)&&(tablero[nuevaFila][nuevaColumna]=='0'))
    {
        tablero[nuevaFila][nuevaColumna] = 'x';
        eliminadas--;
    }
    nuevaFila = fila + 2;
    nuevaColumna = columna + 1;
    if((nuevaFila>=0&&nuevaFila<n)&&(nuevaColumna>=0&&nuevaColumna<n)&&(tablero[nuevaFila][nuevaColumna]=='0'))
    {
        tablero[nuevaFila][nuevaColumna] = 'x';
        eliminadas--;
    }
    nuevaFila = fila + 1;
    nuevaColumna = columna - 2;
    if((nuevaFila>=0&&nuevaFila<n)&&(nuevaColumna>=0&&nuevaColumna<n)&&(tablero[nuevaFila][nuevaColumna]=='0'))
    {
        tablero[nuevaFila][nuevaColumna] = 'x';
        eliminadas--;
    }
    nuevaFila = fila + 1;
    nuevaColumna = columna + 2;
    if((nuevaFila>=0&&nuevaFila<n)&&(nuevaColumna>=0&&nuevaColumna<n)&&(tablero[nuevaFila][nuevaColumna]=='0'))
    {
        tablero[nuevaFila][nuevaColumna] = 'x';
        eliminadas--;
    }
    nuevaFila = fila - 2;
    nuevaColumna = columna - 1;
    if((nuevaFila>=0&&nuevaFila<n)&&(nuevaColumna>=0&&nuevaColumna<n)&&(tablero[nuevaFila][nuevaColumna]=='0'))
    {
        tablero[nuevaFila][nuevaColumna] = 'x';
        eliminadas--;
    }
    nuevaFila = fila - 2;
    nuevaColumna = columna + 1;
    if((nuevaFila>=0&&nuevaFila<n)&&(nuevaColumna>=0&&nuevaColumna<n)&&(tablero[nuevaFila][nuevaColumna]=='0'))
    {
        tablero[nuevaFila][nuevaColumna] = 'x';
        eliminadas--;
    }
    nuevaFila = fila - 1;
    nuevaColumna = columna - 2;
    if((nuevaFila>=0&&nuevaFila<n)&&(nuevaColumna>=0&&nuevaColumna<n)&&(tablero[nuevaFila][nuevaColumna]=='0'))
    {
        tablero[nuevaFila][nuevaColumna] = 'x';
        eliminadas--;
    }
    nuevaFila = fila - 1;
    nuevaColumna = columna + 2;
    if((nuevaFila>=0&&nuevaFila<n)&&(nuevaColumna>=0&&nuevaColumna<n)&&(tablero[nuevaFila][nuevaColumna]=='0'))
    {
        tablero[nuevaFila][nuevaColumna] = 'x';
        eliminadas--;
    }
    return eliminadas;
 }
 
 void imprimirTablero(char **tablero,int n)
 {
     int i,j;
     for(i = 0;i < n;i++)
     {
         printf("\n");
         for(j = 0;j < n;j++)
            printf("[%c]",tablero[i][j]);
     }
     printf("\n");
 }
 
 int maximoCaballos(int totalCaballos[])
 {
     int Maximo,i;
     Maximo = totalCaballos[0];
     for(i = 1;i < MAX_SOLUCIONES;i++)
     {
         if(totalCaballos[i] > Maximo)
            Maximo = totalCaballos[i];
     }
     return Maximo;
 }
 
 

este es el codigo, pero no entiendo como puedo hacer que me saque el maximo posible sin necesidad de cambiar todo el codigo, me costo un poco de trabajo hacerlo y entender como iba a ser el algoritmo y todo, por eso no  quiero empezar desde 0, si pudieran ayudarme se los agradeceria muchisimo

de antemano gracias