// File        : grille.c
// Author      : D. DUVIVIER
// Date        : 19/11/14
// Description : Jeu du sudoku de taille variable pour projet DEVA1 - L2 info
// Copyright (c) 2014 UVHC-LISIC. All rights reserved.
//
#include <stdio.h>
#include <stdlib.h>
#include "grille.h"

// Alloue et initialise la grille passée en paramètre
//
// Une ligne supplémentaire est allouée après la dernière ligne : elle
// contient la suite des caractères à utiliser pour visualiser la grille
// de jeu, par exemple :
// - 1 2 3 4 5 6 7 8 9
// - 1 2 3 4 5 6 7 8 9 A B C D E F G
// Le symbole '0' indique une case vide
//
void initGrille(TGrille *grille, const unsigned int GTaille)
{
    unsigned int l, c; // lignes, colonnes

    *grille = calloc(GTaille + 1, sizeof(char *)); // Allocation 1ère dimension du tableau
    if (*grille == NULL)
    {
        fprintf(stderr,"#\n# ERREUR: initGrille() - Impossible d'allouer le tableau contenant la grille !\n#\n");
        abort();
    }

    for (l = 0; l <= GTaille; l++)
    {
        (*grille)[l] = calloc(GTaille, sizeof(char)); // Allocation 2ème dimension du tableau
        if ((*grille)[l] == NULL)
        {
            fprintf(stderr,"#\n# ERREUR: initGrille() - Impossible d'allouer le tableau contenant la grille !\n#\n");
            abort();
        }
        for (c = 0; c < GTaille; c++)
            (*grille)[l][c] = '0';
    }
}

// Détruit/désalloue le contenu de la grille passée en paramètre
void supprimeGrille(TGrille *grille, const unsigned int GTaille)
{
    unsigned int l; // lignes

    for (l = 0; l <= GTaille; l++)
        free((*grille)[l]); // Libère/désalloue 2ème dimension du tableau

    free(*grille);  // Libère/désalloue 1ère dimension du tableau
    *grille = NULL; // Pour y interdire de futurs accès
}

// Affiche la grille de jeu
void afficheGrille(const TGrille grille,
                   const unsigned int GTaille, const unsigned int RTaille)
{
    unsigned int r, l, c;
    for (r=0; r<2; r++)
    {
        printf("++");
        for (c = 0; c < GTaille; c++)
        {
            if ((c % RTaille) != RTaille - 1)
                printf("---+");
            else
                printf("---++");
        }
        puts("");
    }
    for (l = 0; l < GTaille; l++)
    {
        printf("||");
        for (c = 0; c < GTaille; c++)
        {
            if ((c % RTaille) != RTaille - 1)
            {
                if (grille[l][c] != '0')
                    printf(" %c |", grille[l][c]);
                else
                    printf("   |");
            }
            else
            {
                if (grille[l][c] != '0')
                    printf(" %c ||", grille[l][c]);
                else
                    printf("   ||");
            }
        }
        puts("");
        for (r=0; r < 1 + ((l % RTaille) == RTaille - 1); r++)
        {
            printf("++");
            for (c = 0; c < GTaille; c++)
            {
                if ((c % RTaille) != RTaille - 1)
                    printf("---+");
                else
                    printf("---++");
            }
            puts("");
        }
    }
    puts("");
}

// Affiche la liste des caractères utilisables dans la grille de jeu
void affichelistecaracteres(const TGrille grille, const unsigned int GTaille)
{
    unsigned int c;

    printf("+");
    for (c = 0; c < GTaille; c++)
        printf("---+");
    puts("");
    printf("|");
    for (c = 0; c < GTaille; c++)
    {
        if (grille[GTaille][c] != '0')
            printf(" %c |", grille[GTaille][c]);
        else
            printf("   |");
    }
    puts("");
    printf("+");
    for (c = 0; c < GTaille; c++)
        printf("---+");
    puts("");
}

// Convertit un N° de plan (entre 1 et GTaille)
// en un caractère utilisable dans la grille de jeu
//
// Retourne '\0' si le numéro de plan est incorrect
//
char plan2char(const TGrille grille, const unsigned int GTaille,
               const unsigned int plan)
{
    if ((plan < 1) || (plan > GTaille))
        return '\0';

    return grille[GTaille][plan-1];
}

// Convertit un caractère (symbole situé dans la grille de jeu)
// en un N° de plan (entre 1 et GTaille)
// en un caractère utilisable dans la grille de jeu
//
// La suite des symboles n'est pas nécessairement triée, ce qui
// fait que cette fonction utilise une recherche séquentielle dans
// un tableau d'éléments non triés (non efficace).
//
// Retourne '0' si le caractère incorrect
//
unsigned int char2plan(const TGrille grille, const unsigned int GTaille,
                       const char code)
{
    unsigned int plan;

    for (plan=1; plan<=GTaille; plan++)
        if (grille[GTaille][plan-1] == code)
            return plan;

    return 0; // Non trouvé !
}


// Retourne vrai (1) si le symbole N°"plan" peut être placé
// dans la ligne "ligne" sur la grille de jeu
// faux (0) sinon
// (plan doit être compris entre 1 et GTaille,
// ligne doit être comprise entre 0 et GTaille-1)
bool symboleautoriseenligne(const TGrille grille, const unsigned int GTaille,
                            const unsigned int ligne,
                            const unsigned int plan)
{
    unsigned int c;

}

// Retourne vrai (1) si le symbole N°"plan" peut être placé
// dans la colonne "colonne" sur la grille de jeu
// faux (0) sinon
// (plan doit être compris entre 1 et GTaille,
// colonne doit être comprise entre 0 et GTaille-1)
bool symboleautoriseencolonne(const TGrille grille, const unsigned int GTaille,
                              const unsigned int colonne,
                              const unsigned int plan)
{
    unsigned int l;

}

// Retourne vrai (1) si le symbole N°"plan" peut être placé
// dans la région à laquelle appartient le couple "(ligne, colonne)"
// faux (0) sinon
// (plan doit être compris entre 1 et GTaille)
//
// ligne et colonne doivent être comprises entre 0 et GTaille-1
//
bool symboleautoriseenregion(const TGrille grille,
                             const unsigned int GTaille,
                             const unsigned int RTaille,
                             const unsigned int ligne,
                             const unsigned int colonne,
                             const unsigned int plan)
{
    unsigned int rligne, rcolonne; // Position en haut à gauche de la région
    unsigned int ltmp, ctmp; // Calcul temporaire du multiple de RTaille
    unsigned int m, n; // ligne "modulo RTaille" et colonne "modulo RTaille"

    ltmp = ligne / RTaille;
    ctmp = colonne / RTaille;
    rligne = ltmp * RTaille;
    rcolonne = ctmp * RTaille;
    for (m=0; m<RTaille; m++)
        for (n=0; n<RTaille; n++)
            if (grille[rligne+m][rcolonne+n] == plan2char(grille, GTaille, plan))
                return false; // Inutile de continuer, le résultat est "faux"

    return true;
}

// Vérifie l'unicité des chiffres déjà placés dans la grilles par région.
// Retourne vrai (1) s'il n'y a aucun doublon dans la
// région 3 x 3 dont la case située en haut à gauche est située à la position
// (rligne, rcolonne) dans la grille du sudoku.
//
// rligne et rcolonne doivent être comprises entre 0 et GTaille-1
//
// ATTENTION : Il manque des tests de "validité"
// (notamment les codes de retour de char2plan en cas de problème)
//
bool verifieUniciteRegion(const TGrille grille,
                          const unsigned int GTaille,
                          const unsigned int RTaille,
                          const unsigned int rligne,
                          const unsigned int rcolonne)
{
    unsigned int p;
    unsigned int m, n; // ligne "modulo RTaille" et colonne "modulo RTaille"

    Tusint Toccurrences[GTaille+1]; // Tableau d'occurrences ATTENTION : GTaille+1

    // Ci-dessous, la boucle doit commencer à 0 et terminer à GTaille !!!
    for (p = 0; p <= GTaille; p++)
        Toccurrences[p] = 0;

    for (m=0; m<RTaille; m++)
        for (n=0; n<RTaille; n++)
            Toccurrences[char2plan(grille, GTaille, grille[rligne+m][rcolonne+n])] ++;

    // Ci-dessous, la boucle doit commencer à 1 et terminer à GTaille !!!
    for (p = 1; p <= GTaille; p++)
        if (Toccurrences[p] > 1) {
            printf("le caractere %d dans la region %d est en doublon\n",p,grille[rligne+1][rcolonne+1]);
            return false;
        }

    return true;
}

// Fonction qui verifie l'unicité d'une Colonne
bool verifieUniciteColonne(const TGrille grille,
                           const unsigned int GTaille,
                           const unsigned int rligne,
                           const unsigned int rcolonne)
{
    unsigned int p = 0;
    unsigned int m; // ligne "modulo RTaille" et colonne "modulo RTaille"

    Tusint Toccurrences[GTaille+1]; // Tableau d'occurrences ATTENTION : GTaille+1

    // Ci-dessous, la boucle doit commencer à 0 et terminer à GTaille !!!
    for (p = 0; p <= GTaille; p++)
        Toccurrences[p] = 0;

    for (m=0; m<GTaille; m++)
        Toccurrences[char2plan(grille, GTaille, grille[rligne+m][rcolonne])] ++;

    // Ci-dessous, la boucle doit commencer à 1 et terminer à GTaille !!!
    for (p = 1; p <= GTaille; p++)
        if (Toccurrences[p] > 1)
        {
            printf("le caractere %d sur la colonne %d est en doublon\n",p,rcolonne+1);
            return false;
        }

    return true;
}
// Fonction qui verifie l'unicité d'une Ligne
bool verifieUniciteLigne(const TGrille grille,
                         const unsigned int GTaille,
                         const unsigned int rligne,
                         const unsigned int rcolonne)
{
    unsigned int p;
    unsigned int n; // ligne "modulo RTaille" et colonne "modulo RTaille"

    Tusint Toccurrences[GTaille+1]; // Tableau d'occurrences ATTENTION : GTaille+1

    // Ci-dessous, la boucle doit commencer à 0 et terminer à GTaille !!!
    for (p = 0; p <= GTaille; p++)
        Toccurrences[p] = 0;

    for (n=0; n<GTaille; n++)
        Toccurrences[char2plan(grille, GTaille, grille[rligne][rcolonne+n])] ++;

    // Ci-dessous, la boucle doit commencer à 1 et terminer à GTaille !!!
    for (p = 1; p <= GTaille; p++)
        if (Toccurrences[p] > 1)
        {
            return false;
        }

    return true;
}


// Vérifie l'unicité des chiffres déjà placés dans la grille
// - en ligne
// - en colonnes
// - par région
//
// Retourne faux/false en cas d'erreur (doublon(s) sur la grille)
// et un affichage indique où est le problème.
bool verifieUnicite(const TGrille grille,
                    const unsigned int GTaille,
                    const unsigned int RTaille)
{
    unsigned int l, c, p;
    bool Tunique[GTaille+1]; // ATTENTION : GTaille+1 !!!

    Tunique[0] = false;

    // Vérification en ligne
    for(l=0; l<GTaille; l++)
    {
        Tunique[l] = verifieUniciteLigne(grille,GTaille,l,0);
        if(Tunique[l] == false)
        {
            return false;
        }
    }

    // Vérification en colonne
    for(c=0; c<GTaille; c++)
    {
        Tunique[c] = verifieUniciteColonne(grille,GTaille,0,c);
        if(Tunique[c] == false)
        {
            return false;
        }
    }
    // Vérification par région
    for(l=0; l<GTaille; l=l+RTaille)
    {
        for(c=0; c<GTaille; c=RTaille)
        {
            p++;
            Tunique[p] = verifieUniciteRegion(grille,GTaille,RTaille,l,c);
            if(Tunique[p] == false)
            {
                printf("Il y a un doublon dans la region %d\n",p);
                return false;
            }
        }
    }
    return true;
}



// Vérifie si la grille est complête ou non.
// Cette fonction est nécessaire car le plan 0 de la grille3D peut être rempli
// de 0 dans deux cas : soit il n'y a plus aucune possibilité de jeu, mais la
// grille (2D) n'est pas pleine en raison de l'impossibilité de complêter la
// grille (grille infaisable) ou la grille (2D) est pleine et en ce cas la
// résolution est terminée (grille faisable, et trouvée !).
// Cette fonction détecte le cas où la grille est terminée & faisable.
//
bool grilleComplete(const TGrille grille,
                    const unsigned int GTaille)
{
    unsigned int l, c, cumul = 0;

    for (l = 0; l < GTaille; l++)
        for (c = 0; c < GTaille; c++)
            if (grille[l][c] != '0')
                cumul++;
    return cumul == GTaille * GTaille;
}