c-doku.c

1、较复杂的数独游戏

            tab[k] = 0;
        }

        // On parcourt la colonne en cours
        for(i=0;i<taille;i++)
        {
            elimine(grille,i,j,zonex,zoney,zoneh,zonel,taille);
            // Si la case possede plusieurs candidats
            if(grille[i][j].affiche == 0)
            {
                // On parcourt le tableau des candidats de la case
                for(k=1;k<taille+1;k++)
                {
                    // On cherche les candidats possibles
                    if(grille[i][j].tab[k] !=0)
                    {
                        // Et on l'ajoute a sa place dans le tableau des occurences
                        tab[k] = tab[k] + 1;
                    }
                }
            }
        }

        // On parcourt la colonne de nouveau
        for(i=0;i<taille;i++)
        {
            // Si la case possede plusieurs candidats
            if(grille[i][j].affiche == 0)
            {
                // On parcourt le tableau des candidats de la case
                for(k=1;k<taille+1;k++)
                {
                    // On va comparer les candidats avec le tableau des occurences
                    if(grille[i][j].tab[k] == 1)
                    {
                        // Si c'est un unique, et qu'il est present sur cette case
                        if(tab[k] == 1)
                        {
                            // Alors on le valide
                            grille[i][j].affiche = k;
                            // On ajoute le coup a l'historique de resolution
                            histpc = ajoutcoup(grille,taille,histpc,nombrecoup(histpc)+1,k,i,j,4);
                            return(1);
                        }
                    }
                }
            }
        }
    }
    return(0);
}

// Verifie que la grille a ete resolue completement
// Renvoie 0 si la grille n'est pas remplie totalement
// Renvoie 1 si la grille est correctement remplie
// Renvoie 2 en cas de mauvaise supposition par la methode de backtracking
int verifie(cell **grille, int zonex, int zoney, int zoneh, int zonel, int taille)
{
    int i = 0;
    int j = 0;
    int k = 0;
    int m = 0;
    int occurence[10];
    int sommeposs = 0;
    int tabtemp[10];

    // RAZ du tableau des possibilites
    raztab(grille,taille);

    for(i=0;i<taille;i++)
    {
        for(j=0;j<taille;j++)
        {
            if(grille[i][j].affiche == 0)
            {
                sommeposs = 0;
                for(k=0;k<(taille+1);k++)
                {
                    if(grille[i][j].tab[k] == 1)
                    {
                        // et on insere ces possibilites restantes
                        // dans un tableau temporaire
                        tabtemp[sommeposs] = k;
                        sommeposs++;
                    }
                }
                if(sommeposs == 0)
                {
                    // Si la somme est egale a zero, c'est qu'il y une erreur
                    // on retourne donc 2 pour le faire savoir a la fontion appelante
                    return(2);
                }
            }
            k = 0;
            do
            {
                // Etape 1 : on elimine les possibilites de la ligne
                if(k == 0)
                {
                    elimineligne(grille,i,j,taille);
                }
                // Etape 2 : on elimine les possibilites de la colonne
                if(k == 1)
                {
                    eliminecolonne(grille,i,j,taille);
                }
                // Etape 3 : on elimine les possibilites de la zone
                if(k == 2)
                {
                    eliminezone(grille,i,j,zonex,zoney,zoneh,zonel,taille);
                }
                // Apres chaque etape, on somme le nombre de possibilites.
                // Normalement, si la grille a ete correctement et completement
                // resolue il ne doit plus y avoir de possibilites restantes
                for(m=1;m<taille+1;m++)
                {
                    // S'il en reste, on renvoie 0
                    if(grille[i][j].tab[m] == 1)
                    {
                        return 0;
                    }
                }
                k++;
            }while(k != 3);
        }
    }
    // Si tout s'est bien deroule, on renvoie 1
    return 1;
}

// Verifie s'il existe des cases auxquelles ils restent "nb" possibilites
// Renvoie ce nombre de cases ou
// Renvoie -1 en cas d'erreur (aucune possibilite alors que la case n'est pas affichee)
int sommecase(cell **grille, int zonex, int zoney, int zoneh, int zonel, int taille, int nb)
{
    int i = 0;
    int j = 0;
    int k = 0;
    int sommecase = 0;
    int sommeposs = 0;

    for(i=0;i<taille;i++)
    {
        for(j=0;j<taille;j++)
        {
            if(grille[i][j].affiche == 0)
            {
                sommeposs = 0;
                for(k=0;k<(taille+1);k++)
                {
                     // On fait la somme des possibilites restantes
                     if(grille[i][j].tab[k] == 1)
                     {
                         sommeposs++;
                     }
                }
                // Si la somme des possibilites restantes correspond au nombre voulu
                // on incremente sommecase, qu'on renverra a la fin
                if(sommeposs == nb)
                {
                    sommecase++;
                }
                if(sommeposs == 0)
                {
                    return(-1);
                }
            }
        }
    }
    return sommecase;
}

/*
    Methode de resolution par supposition (backtraking):
    -   On regarde les cases dans lesquelles il n'y a que 2 candidats possibles,
        et on essaye alors un des deux chiffres et on relance la fonction recursivement,
        qui va retenter la resolution par la methode logique
    -   On procede ainsi de suite jusqu'a ce qu'il y ait un probleme : si une case
        vide n'a plus aucune possibilite, on revient en arriere en mettant l'autre
        chiffre dans la case.
*/

// Renvoie 1 si la methode a fonctionnee
// Renvoie 2 si une mauvaise supposition a ete faite
int resoudback(cell **grille, int zonex, int zoney, int zoneh, int zonel, int taille, comptage *compte)
{
    int i = 0;
    int j = 0;
    int k = 0;
    int m = 0;
    int n = 1;
    int tabtemp[10];
    int valide = 0;

    int somme = 0;
    int sommeposs = 0;

    // Tableau temporaire de sauvegarde de grilles
    int *tabgrille;
    tabgrille = (int*)malloc((taille*taille)*sizeof(int));

    do
    {
        // Somme les cases ayant "n" possibilites restantes
        somme = sommecase(grille,zonex,zoney,zoneh,zonel,taille,n);
        if(somme == 0)
        {
            // S'il n'y en a plus, on passe aux cases en ayant "n+1"
            n++;
        }
        if(somme == -1)
        {
            // S'il y a une erreur, on renvoie 2
            return 2;
        }
    }
    while(somme == 0);

    raztab(grille,taille);

    for(i=0;i<taille;i++)
    {
        for(j=0;j<taille;j++)
        {
            // Si case vide, on la traite
            if(grille[i][j].affiche == 0)
            {
                // On elimine les possibilites de la case
                elimine(grille,i,j,zonex,zoney,zoneh,zonel,taille);

                // On fait la somme des possibilites restantes de la case
                sommeposs = 0;
                for(k=0;k<(taille+1);k++)
                {
                    if(grille[i][j].tab[k] == 1)
                    {
                        // et on insere ces possibilites restantes
                        // dans un tableau temporaire
                        tabtemp[sommeposs] = k;
                        sommeposs++;
                    }
                }

                // Si la somme des possibilites restantes est egale a 0,
                // c'est qu'il y a eu une mauvaise supposition a un moment
                // dans la recursivite, donc on sort en renvoyant 2
                if(sommeposs == 0)
                {
                    return 2;
                }

                // Si le nombre de possibilites restantes de la case correspond
                // a "n", on traite la case
                if(sommeposs == n)
                {
                    m = 0;
                    do
                    {
                        // On sauvegarde la grille actuelle
                        // pour pouvoir revenir en cas de mauvaise supposition
                        sauvegrille(grille,taille,tabgrille);
                        // On va faire une supposition, on a ajoute 1 au comptage
                        compte->lb = compte->lb+1;

                        // On commence la methode par supposition :
                        // on inscrit une possibilite dans la case en allant
                        // chercher dans notre tableau temporaire,
                        grille[i][j].affiche = tabtemp[m];
                        // On ajoute ce coup a l'historique
                        histpc = ajoutcoup(grille,taille,histpc,nombrecoup(histpc)+1,tabtemp[m],i,j,5);

                        // On appelle la fonction de maniere recursive
                        valide = resoudtout(grille,zonex,zoney,zoneh,zonel,taille,compte);

                        // Si le chiffre 2 est retourne, la supposition precedente
                        // etait mauvaise, alors on charge la grille precedente
                        if(valide == 2)
                        {
                            chargegrille(grille,taille,tabgrille);
                            // Du coup, on enleve 1 au comptage
                            compte->lb = compte->lb-1;
                            // et comme "m" va etre incremente a la sortie du switch,
                            // on va pouvoir tester la supposition
                            // suivante du tableau temporaire
                        }

                        // Si le chiffre 1 est retourne, la methode logique
                        // a permis de finir la resolution donc on retourne 1
                        // pour sortir de toutes les fonctions ouvertes
                        if(valide == 1)
                        {
                            return 1;
                        }

                        // Si on a traite toutes les possibilites de la case
                        // et que cela n'a rien donne, on revient en arriere
                        if(m+1 == n)
                        {
                            return 2;
                        }
                        m++;
                    // On incremente "m" tant qu'il n'est pas egal a "n"
                    }
                    while(m != n);
                }
            }
        }
    }
}


/*
    Fonction de resolution complete de la grille:
    -   Tente en premier les methodes de resolution logique qui suffisent a la plupart des grilles
    -   Si cela n'est pas suffisant, lance la methode par supposition
    Renvoie 1 en cas de resolution reussie
*/

int resoudtout(cell **grille, int zonex, int zoney, int zoneh, int zonel, int taille, comptage *compte)
{
    int i = 0;
    int r = 0;
    int v = 0;

    // On commence par verifier si la grille a ete correctement et completement remplie
    v = verifie(grille,zonex,zoney,zoneh,zonel,taille);

    // Si c'est le cas, on renvoie 1
    if(v == 1)
    {
        return(1);
    }

    // Si une mauvaise supposition a ete faite on renvoie 2
    if(v == 2)
    {
        return(2);
    }

    // On lance la premiere methode de resolution logique
    if(logique1(grille,zonex,zoney,zoneh,zonel,taille) != 0)
    {
        // Ajoute 1 au comptage
        compte->l = compte->l+1;
        if(resoudtout(grille,zonex,zoney,zoneh,zonel,taille,compte) == 1)
        {
            // On relance recursivement la fonction, et si celle ci renvoie 1
            // on sort
            return(1);
        }
    }

    // On lance la seconde methode de resolution logique sur les lignes
    if(logiquelignes(grille,zonex,zoney,zoneh,zonel,taille) != 0)
    {
        // Ajoute 1 au comptage
        compte->ll = compte->ll+1;
        if(resoudtout(grille,zonex,zoney,zoneh,zonel,taille,compte) == 1)
        {
            // On relance recursivement la fonction, et si celle ci renvoie 1
            // on sort
            return(1);
        }
    }

    // On lance la seconde methode de resolution logique sur les colonnes
    if(logiquecolonnes(grille,zonex,zoney,zoneh,zonel,taille) != 0)
    {
        // Ajoute 1 au comptage
        compte->lc = compte->lc+1;
        if(resoudtout(grille,zonex,zoney,zoneh,zonel,taille,compte) == 1)
        {
            // On relance recursivement la fonction, et si celle ci renvoie 1
            // on sort
            return(1);
        }
    }

    // On lance la methode par supposition
    r = resoudback(grille,zonex,zoney,zoneh,zonel,taille,compte);
    return(r);
}


/*
    Ensemble de fonctions
    permettant la generation d'une grille de difficulte variable
    suivant la demande de l'utilisateur
*/

// Enleve des case par symetrie centrale suivant un niveau de difficulte
void enleve(cell **grille, int zonex, int zoney, int zoneh, int zonel, int taille, comptage *compte, int niveau)
{
    int i = 0;
    int j = 0;
    int boucle = 1;

    // Tableau de sauvegarde temporaire d'une grille
    int *tabgrille;
    tabgrille = (int*)malloc((taille*taille)*sizeof(int));

    // Tableau de sauvegarde temporaire d'une grille
    int *tabvalide;
    tabvalide = (int*)malloc((taille*taille)*sizeof(int));

    // On sauvegarde la grille complete pour commencer
    sauvegrille(grille,taille,tabgrille);

    // On remet a zero le comptage pour determiner la difficulte
    razcompte(compte);