c-doku.c

1、较复杂的数独游戏

/***
 *** Fichier:
 *** c-doku.c
 ***
 *** Projet:
 *** C-doku
 ***
 *** Licence:
 *** GNU GENERAL PUBLIC LICENSE
 ***
 *** Auteurs:
 *** BEUGNET Pierre
 *** POLONOWSKI Raphael
 ***
 ***/

// Librairie de maniement des chaines
#include <string.h>
// Librairie d'entrees/sorties
#include <stdio.h>
// Librairie nous servant principalement pour l'allocation dynamique de m閙oire
#include <stdlib.h>
// Librairie utilisee pour la generation aleatoire de nombres
#include <time.h>
// Librairie graphique du jeu
#include <allegro.h>
#include <limits.h>
#include <stdarg.h>
#include "adime.h"


/*
    Declarations des differentes
    structures de donnees
*/

// Grille de sudoku
typedef struct sudoku
{
    //Coordonnees graphiques de la case
    int x;
    int y;
    //Candidats possibles pour la case
    int tab[10];
    //Valeur certaine de la case (0 si plusieurs candidats)
    int affiche;
    //Indique si la case appartient au Sudoku cree
    int bloquee;
}
cell;

// Pointeur vers l'historique des coups
typedef struct coup* pcoup;
// Liste des coups joues
typedef struct coup
{
    // Numero du coup joue
    int nb;
    // Nombre ajoute
    int affiche;
    // Coordonnee de la case
    int x,y;
    // Methode utilisee
    int methode;
    // Grille a l'instant du coup
    int tabgrille[81];
    pcoup suivant;
}
tcoup;

// Pointeur vers historique des coups joues
pcoup hist = NULL;
pcoup histpc = NULL;

// Structure de comptage
typedef struct
{
    // Nombre d'utilisation de la premiere methode logique
    int l;
    // Nombre d'utilisation de la methode logique colonnes
    int lc;
    // Nombre d'utilisation de la methode logique lignes
    int ll;
    // Nombre d'utilisation de la methode par backtracking
    int lb;
}
comptage;


/*
    Ensemble de fonctions
    gerant la grille de sudoku
    (creation, initialisation, affichage, sauvegarde et chargement, ...)
*/

// Cree une grille vierge et renvoie un pointeur vers celle-ci
cell** creegrille(int taille)
{
    cell **grille;

    int i = 0;

    grille = malloc(taille*sizeof(cell*));
    for(i=0;i<taille;i++)
    {
        grille[i] = calloc(taille, sizeof(cell));
    }

    return(grille);
}

// Remet a zero le comptage
void razcompte(comptage *compte)
{
    compte->l = 0;
    compte->lc = 0;
    compte->ll = 0;
    compte->lb = 0;
}

// Calcule largeur et hauteur d'une zone suivant la taille de la grille
void largeurzone(int taille, int *zoneh, int *zonel)
{
    switch(taille)
    {
        case 4 :
        *zoneh=2;
        *zonel=2;
        break;
        case 6 :
        *zoneh=2;
        *zonel=3;
        break;
        case 9 :
        *zoneh=3;
        *zonel=3;
        break;
        case 15:
        *zoneh=5;
        *zonel=3;
        break;
    }
}

// Calcule les coordonnes de la zone suivant la case envoyee en parametres
void testzone(cell **grille, int casex, int casey, int *zonex, int *zoney, int zoneh, int zonel)
{
    *zonex=casex/zoneh;
    *zoney=casey/zonel;
}

// Affiche l'ensemble de la grille en mode graphique
void affichegrille_allegro(cell **grille, int taille, int niveau, int type, int controle_actif, BITMAP* buffer, BITMAP* fond, BITMAP* _1, BITMAP* _2, BITMAP* _3, BITMAP* _4, BITMAP* _5, BITMAP* _6, BITMAP* _7, BITMAP* _8, BITMAP* _9)
{
    int i=0;
    int j=0;

    // On affiche le fond correspondant a la taille de la grille
    draw_sprite(buffer,fond,0,0);

    // On affiche les chiffres de la grille a l'ecran grace aux coordonnees
    for(i=0;i<taille;i++)
    {
        for(j=0;j<taille;j++)
        {
            switch(grille[i][j].affiche)
            {
                case 1 : draw_sprite(buffer,_1,grille[i][j].x,grille[i][j].y);
                break;
                case 2 : draw_sprite(buffer,_2,grille[i][j].x,grille[i][j].y);
                break;
                case 3 : draw_sprite(buffer,_3,grille[i][j].x,grille[i][j].y);
                break;
                case 4 : draw_sprite(buffer,_4,grille[i][j].x,grille[i][j].y);
                break;
                case 5 : draw_sprite(buffer,_5,grille[i][j].x,grille[i][j].y);
                break;
                case 6 : draw_sprite(buffer,_6,grille[i][j].x,grille[i][j].y);
                break;
                case 7 : draw_sprite(buffer,_7,grille[i][j].x,grille[i][j].y);
                break;
                case 8 : draw_sprite(buffer,_8,grille[i][j].x,grille[i][j].y);
                break;
                case 9 : draw_sprite(buffer,_9,grille[i][j].x,grille[i][j].y);
                break;
            }
        }
    }

    // On affiche les cases de selection du chiffre chiffre a entrer, suivant la taille
    switch(taille)
    {
        case 4 :
                draw_sprite(buffer,_1,426,200);
                draw_sprite(buffer,_2,469,200);
                draw_sprite(buffer,_3,426,243);
                draw_sprite(buffer,_4,469,243);
        break;
        case 6 :
                draw_sprite(buffer,_1,510,290);
                draw_sprite(buffer,_2,553,290);
                draw_sprite(buffer,_3,596,290);
                draw_sprite(buffer,_4,510,333);
                draw_sprite(buffer,_5,553,333);
                draw_sprite(buffer,_6,596,333);
        break;
        case 9 :
                draw_sprite(buffer,_1,647,379);
                draw_sprite(buffer,_2,690,379);
                draw_sprite(buffer,_3,733,379);
                draw_sprite(buffer,_4,647,422);
                draw_sprite(buffer,_5,690,422);
                draw_sprite(buffer,_6,733,422);
                draw_sprite(buffer,_7,647,465);
                draw_sprite(buffer,_8,690,465);
                draw_sprite(buffer,_9,733,465);
        break;
    }

    // On affiche les informations dans la zone d'infos a gauche de la grille
    textprintf_ex(buffer,font, 10, 140, makecol(0, 0, 0),-1, "--- Taille ---");
    textprintf_ex(buffer,font, 10, 160, makecol(0, 0, 0),-1, "%i",taille);
    textprintf_ex(buffer,font, 10, 180, makecol(0, 0, 0),-1, "--- Niveau ---");
    switch(niveau)
    {
        case 1 : textprintf_ex(buffer,font, 10, 200, makecol(0, 0, 0),-1, "Tres facile");
        break;
        case 2 : textprintf_ex(buffer,font, 10, 200, makecol(0, 0, 0),-1, "Facile");
        break;
        case 3 : textprintf_ex(buffer,font, 10, 200, makecol(0, 0, 0),-1, "Moyen");
        break;
        case 4 : textprintf_ex(buffer,font, 10, 200, makecol(0, 0, 0),-1, "Difficile");
        break;
        case 5 : textprintf_ex(buffer,font, 10, 200, makecol(0, 0, 0),-1, "Tres difficile");
        break;
        case 6 : textprintf_ex(buffer,font, 10, 200, makecol(0, 0, 0),-1, "Grille vide");
        break;
    }
    textprintf_ex(buffer,font, 10, 220, makecol(0, 0, 0),-1, "---- Type ----");
    switch(type)
    {
        case 1 : textprintf_ex(buffer,font, 10, 240, makecol(0, 0, 0),-1, "Chiffres");
        break;
        case 2 : textprintf_ex(buffer,font, 10, 240, makecol(0, 0, 0),-1, "Lettres");
        break;
        case 3 : textprintf_ex(buffer,font, 10, 240, makecol(0, 0, 0),-1, "Images");
        break;
    }
    textprintf_ex(buffer,font, 10, 260, makecol(0, 0, 0),-1, "-- Controle --");
    switch(controle_actif)
    {
        case 0 : textprintf_ex(buffer,font, 10, 280, makecol(0, 0, 0),-1, "Sans");
        break;
        case 1 : textprintf_ex(buffer,font, 10, 280, makecol(0, 0, 0),-1, "Avec");
        break;
    }
    textprintf_ex(buffer,font, 5, 310, makecol(0, 0, 0),-1, "---- Cases ----");
    textprintf_ex(buffer,font, 5, 320, makecol(0, 0, 0),-1, "---- vides ----");
    textprintf_ex(buffer,font, 10, 340, makecol(0, 0, 0),-1, "%i",(taille*taille)-casesrestantes(grille,taille));
}

// Fonction de sauvegarde temporaire d'une grille dans un tableau
void sauvegrille(cell **grille, int taille, int *tabgrille)
{
    int i = 0;
    int j = 0;
    int k = 0;

    for(i=0;i<taille;i++)
    {
        for(j=0;j<taille;j++)
        {
            tabgrille[k] = grille[i][j].affiche;
            k++;
        }
    }
}

// Fonction de chargement d'un tableau vers une grille
void chargegrille(cell **grille, int taille, int *tabgrille)
{
    int i = 0;
    int j = 0;
    int k = 0;

    for(i=0;i<taille;i++)
    {
        for(j=0;j<taille;j++)
        {
            grille[i][j].affiche = tabgrille[k];
            k++;
        }
    }
}

// Remise a zero du tableau des possibilites de toutes les cases
void raztab(cell **grille, int taille)
{
    int i = 0;
    int j = 0;
    int k = 0;

    for(i=0;i<taille;i++)
    {
        for(j=0;j<taille;j++)
        {
            grille[i][j].tab[0] = 0;
            for(k=1;k<(taille+1);k++)
            {
                // L'indice representera la possibilite
                // et la case contiendra un 1 si la possibilite est encore valide
                // 0 sinon
                grille[i][j].tab[k] = 1;
            }
        }
    }
}

// Remize a zero de la grille complete
void razgrille(cell **grille, int taille)
{
    int i = 0;
    int j = 0;

    for(i=0;i<taille;i++)
    {
        for(j=0;j<taille;j++)
        {
            grille[i][j].affiche = 0;
        }
    }
}

// Renvoie le nombre de cases remplies
int casesrestantes(cell **grille, int taille)
{
    int i = 0;
    int j = 0;
    int k = 0;

    for(i=0;i<taille;i++)
    {
        for(j=0;j<taille;j++)
        {
            if(grille[i][j].affiche != 0)
            {
                k++;
            }
        }
    }
    return k;
}

// Controle les regles du Sudoku
int controle(cell **grille, int zoneh, int zonel, int taille, int *ligne, int *colonne, int *valeur)
{
    int tab[10];
    int i = 0;
    int j = 0;
    int k = 1;
    int zonex = 0;
    int zoney = 0;
    int a,b;

    // On parcourt l'ensemble des lignes
    for(i=0;i<taille;i++)
    {
        // Remise a zero du tableau des occurences de la ligne
        for(j=1;j<taille+1;j++)
        {
            tab[j] = 0;
        }

        // On parcourt la ligne en cours
        for(j=0;j<taille;j++)
        {
            // Si la case possede un chiffre
            if(grille[i][j].affiche != 0)
            {
                // On l'ajoute au tableau des occurences de la ligne
                tab[grille[i][j].affiche] = tab[grille[i][j].affiche] + 1;
            }
        }

        // A la fin de la ligne, on parcourt le tableau pour v閞ifier qu'il n'y
        // a pas de chiffres en double
        for(j=1;j<(taille+1);j++)
        {
            // Si un chiffre est en double, ou plus, on retourne 1
            if(tab[j] > 1)
            {
                *valeur = j;
                *ligne  = i;
                return 1;
            }
        }
    }

    // On parcourt l'ensemble des colonnes
    for(j=0;j<taille;j++)
    {
        // Remise a zero du tableau des occurences de la colonne
        for(i=0;i<10;i++)
        {
            tab[i] = 0;
        }

        // On parcourt la colonne en cours
        for(i=0;i<taille;i++)
        {
            // Si la case possede un chiffre