Jogo Lights Out em C

[AndG]

Olá

Preciso de uma ajuda para resolver esse jogo.

Preciso implementar uma função de ajuda ao usuário. Essa função deve resolver o programa de todas as formas possíveis contabilizando-as e no final mostrar a solução com menor número de passos, caso essa solução exista.

Tentei fazer por força bruta mas sem sucesso.

O programa já pronto é este: http://www.ime.usp.br/~coelho/mac0122-2014/ep1/executavel/lightout-windows.exe

O código do que fiz até agora é o seguinte:

void resolvaTurtledorm(int nLin, int nCol, int tDorm[][MAX])
{
    int z = ACORDADO, numero_tapinhas = 1, numero_solucoes = 0, numero_tapinhas_solucao, execucao = 1, matrizteste[MAX][MAX], matrizsolucao[MAX][MAX], matrizaguarda[MAX][MAX];
    int a, b, c, d, e, f, g, h;
 
    /* 1 tapinha por vez */
 
    for (a = 0; a < nLin; a++) /* Percorrendo as linhas da matriz teste */
    {
        for (b = 0; b < nCol; b++) /* Percorrendo as colunas da matriz teste */
        {
            tapinhaTurtle(nLin, nCol, matrizteste, a, b); /* Da um tapinha */
            if (todosDormindo(nLin, nCol, matrizteste) == TRUE) /* Verificando se o tapinha resolveu */
            {
                numero_solucoes++; /* Se o tapinha resolveu, incrementa o numero de solucoes e */
                for (c = 0; c < nLin; c++)
                    for (d = 0; d < nCol; d++)
                        matrizsolucao[c][d] = matrizteste[c][d]; /* salva na matriz solucao essa solucao */
                matrizsolucao[a][b] = 2; /* Avisa para a mostreTurtle sobre a posicao que recebeu um tapinha */
                numero_tapinhas_solucao = numero_tapinhas; /* Salva o numero de tapinhas necessarios para resolver */
            }
            tapinhaTurtle(nLin, nCol, matrizteste, a, b); /* Desfaz o tapinha */
        }
    }
 
    /* 2 tapinhas por vez */
 
    for (a = 0; a < nLin; a++)
        for (b = 0; b < nCol; b++)
            matrizaguarda[a][b] = 0;
 
    while (numero_tapinhas <= (nLin * nCol)) /* Numero de vezes que tem que dar tapinhas */
    {
        while (execucao <= numero_tapinhas)
        {
            for (a = 0; a < nLin; a++) /* Percorrendo as linhas da matriz teste */
            {
                for (b = 0; b < nCol; b++) /* Percorrendo as colunas da matriz teste */
                {
                    tapinhaTurtle(nLin, nCol, matrizteste, a, b); /* Da um tapinha */
                    if (matrizteste[a][b] + matrizaguarda[a][b] == 2) /* Atualiza a matriz aguarda com o resultado do tapinha */
                        matrizaguarda[a][b] = 0;
                    else
                        if (matrizteste[a][b] + matrizaguarda[a][b] == 1)
                            matrizaguarda[a][b] = 1;
                        else
                            if (matrizteste[a][b] + matrizaguarda[a][b] == 0)
                                matrizaguarda[a][b] = 0;
                    if (todosDormindo(nLin, nCol, matrizaguarda) == TRUE) /* Verificando se o tapinha resolveu */
                    {
                        numero_solucoes++; /* Se o tapinha resolveu, incrementa o numero de solucoes e */
                        for (c = 0; c < nLin; c++)
                            for (d = 0; d < nCol; d++)
                                matrizsolucao[c][d] = matrizaguarda[c][d]; /* salva na matriz solucao essa solucao */
                        matrizsolucao[a][b] = 2; /* Avisa para a mostreTurtle sobre a posicao que recebeu um tapinha */
                        numero_tapinhas_solucao = numero_tapinhas; /* Salva o numero de tapinhas necessarios para resolver */
                    }
                }
            }
            execucao++;
        }
    }
 
    if (numero_solucoes != 0)
    {
        printf("\nSOLUCAO MENOS VIOLENTA\nForam encontrada(s) %d solucao(oes).\nO menor numero de tapinhas de uma solucao eh %d\n        ", numero_solucoes, numero_tapinhas_solucao);
        mostreTurtledorm(nLin, nCol, matrizsolucao, z);
    }
    else
        printf("Nao tem solucao!\n");
}