/******************************************************************************/ /* NOM */ /* pento */ /******************************************************************************/ /* ADMINISTRATION */ /* Sylvain LHULLIER | 01.12.99 | v01.00 | Creation du programme */ /******************************************************************************/ /******************************************************************************/ /* Fichiers d'en-tete */ /******************************************************************************/ #include #include #include /******************************************************************************/ /* Definitions de constantes */ /******************************************************************************/ #define IMPOSSIBLE 0 #define POSSIBLE 1 #define NB_FAMILLES 12 #define NB_MAX_SOEURS 8 #define NB_MAX_BORDS 16 #define PENTO 5 #define LIBRE '#' #define OCCUPE '.' #define DIM_ERR 1 #define ALLOC_ERR 2 #define FORMAT_ERR 3 #define LECTUR_ERR 4 #define ECRITR_ERR 5 #define OPEN_F_ERR 6 #define FCLOSE_ERR 7 #define MAX_CHAINE 1024 #define OPTION_SOLUTION_UNIQUE 'u' #define OPTION_SANS_SYMETRIE 's' #define OPTION_NOMBRE_SOLUTIONS 'n' #define OPTION_MAN 'h' #define OPTION_FICHIER_SORTIE 'o' /******************************************************************************/ /* Definitions de types */ /******************************************************************************/ typedef struct { int unique; int symetries; int nombre; char *nom_f_sortie; char *nom_f_entree; } Options; typedef struct { int c; int l; } Coord; typedef struct cellule { int *Grille; int NbColonnes; int NbLignes; int H; int V; int D1; int D2; int *clos; int nb_sol; char *buf; void (*Affichage)(FILE*,struct cellule*,Coord*); } Surface; typedef struct { int Min_c; int Max_c; int Max_l; Coord Position[PENTO - 1]; int NbBords; Coord Bords[NB_MAX_BORDS]; } Soeur; typedef struct { int Lettre; int NbSoeurs; int Place; Soeur Formes[NB_MAX_SOEURS]; } Pieces[NB_FAMILLES]; /******************************************************************************/ /* Definition des macros : */ /******************************************************************************/ #define DIMENSIONS_OK(index_piece,index_soeur) \ ( piece[index_piece].Formes[index_soeur].Min_c + colonne >= 0 &&\ piece[index_piece].Formes[index_soeur].Max_c + colonne < C &&\ piece[index_piece].Formes[index_soeur].Max_l + ligne < L ) #define PLACABLE \ ( surface->Grille[(position[0].l + ligne)*C + (position[0].c+colonne)] == LIBRE &&\ surface->Grille[(position[1].l + ligne)*C + (position[1].c+colonne)] == LIBRE &&\ surface->Grille[(position[2].l + ligne)*C + (position[2].c+colonne)] == LIBRE &&\ surface->Grille[(position[3].l + ligne)*C + (position[3].c+colonne)] == LIBRE ) #define PLACER(lettre) \ surface->Grille[ ligne *C + colonne ] = lettre;\ surface->Grille[(position[0].l + ligne)*C + (position[0].c+colonne)] = lettre;\ surface->Grille[(position[1].l + ligne)*C + (position[1].c+colonne)] = lettre;\ surface->Grille[(position[2].l + ligne)*C + (position[2].c+colonne)] = lettre;\ surface->Grille[(position[3].l + ligne)*C + (position[3].c+colonne)] = lettre #define ENLEVER(colonne,ligne) \ surface->Grille[ ligne *C + colonne ] = LIBRE;\ surface->Grille[(position[0].l + ligne)*C + (position[0].c+colonne)] = LIBRE;\ surface->Grille[(position[1].l + ligne)*C + (position[1].c+colonne)] = LIBRE;\ surface->Grille[(position[2].l + ligne)*C + (position[2].c+colonne)] = LIBRE;\ surface->Grille[(position[3].l + ligne)*C + (position[3].c+colonne)] = LIBRE /******************************************************************************/ /* symetries.h */ /******************************************************************************/ /*============================================================================*/ /* Fonction Recherche_Symetries : */ /* But : Recherche des symetries. */ /* Parametres : La surface. */ /* Effets de bord : Initialisation de certains champs de surface. */ /* Valeur de retour : Neant. */ /*============================================================================*/ void Recherche_Symetries( Surface *surface ); /******************************************************************************/ /* pieces.h */ /******************************************************************************/ /*============================================================================*/ /* Fonction Creation_Pieces : */ /* But : Creer la structure des pieces. */ /* Parametres : Aucuns */ /* Effets de bord : Creation de la structure. */ /* Valeur de retour : L'adresse de la structure. */ /*============================================================================*/ Pieces *Creation_Pieces(void); /******************************************************************************/ /* interface.h */ /******************************************************************************/ /*============================================================================*/ /* Fonction Lecture : */ /* But : Lire dans un fichier la figure a paver. */ /* Parametres : Le nom du fichier. */ /* La surface a remplir. */ /* Un pointeur sur int pour dire si elle a ete retournee. */ /* Effets de bord : Initialisation de la surface. */ /* Valeur de retour : 0 si tout s'est bien passe, */ /* Code d'erreur sinon. */ /*============================================================================*/ int Lecture( char *nom_fichier, Surface *surface, int *retournee ); /*============================================================================*/ /* Fonction Affiche_Solution : */ /* But : Affiche une solution dans un fichier. */ /* Parametres : Le fichier. */ /* La surface a afficher. */ /* La position de la croix. */ /* Effets de bord : Affichage d'une ou plusieurs solutions dans le fichier. */ /*============================================================================*/ void Affiche_Solution (FILE *sortie, Surface *surface, Coord *position_croix); /*============================================================================*/ /* Fonction Affiche_Solution_Retournee : */ /* But : Affiche une solution dans un fichier. */ /* Parametres : Le fichier. */ /* La surface a afficher retournee. */ /* La position de la croix. */ /* Effets de bord : Affichage d'une ou plusieurs solutions dans le fichier. */ /*============================================================================*/ void Affiche_Solution_Retournee (FILE* sortie, Surface *surface, Coord *position_croix); /*============================================================================*/ /* Fonction Affiche_Une_Solution : */ /* But : Affiche une solution dans un fichier. */ /* Parametres : Le fichier. */ /* La surface a afficher. */ /* La position de la croix. */ /* Effets de bord : Affichage d'une ou plusieurs solutions dans le fichier. */ /* Ferme le fichier de sortie. */ /* Liberation des structures allouees avec calloc. */ /* Sortie du programme. */ /*============================================================================*/ void Affiche_Une_Solution( FILE* sortie, Surface *surface, Coord *position_croix ); /*============================================================================*/ /* Fonction Affiche_Une_Solution_Retournee : */ /* But : Affiche une solution dans un fichier. */ /* Parametres : Le fichier. */ /* La surface a afficher retournee. */ /* La position de la croix. */ /* Effets de bord : Affichage d'une ou plusieurs solutions dans le fichier. */ /* Ferme le fichier de sortie. */ /* Liberation des structures allouees avec calloc. */ /* Sortie du programme. */ /*============================================================================*/ void Affiche_Une_Solution_Retournee( FILE* sortie, Surface *surface, Coord *position_croix ); /*============================================================================*/ /* Fonction Affiche_Solution_Sans_Symetries : */ /* But : Affiche une solution dans un fichier. */ /* Parametres : Le fichier. */ /* La surface a afficher. */ /* La position de la croix. */ /* Effets de bord : Affichage d'une ou plusieurs solutions dans le fichier. */ /*============================================================================*/ void Affiche_Solution_Sans_Symetries( FILE *sortie, Surface *surface, Coord *position_croix ); /*============================================================================*/ /* Fonction Affiche_Solution_Sans_Symetries_Retournee : */ /* But : Affiche une solution dans un fichier. */ /* Parametres : Le fichier. */ /* La surface a afficher retournee. */ /* La position de la croix. */ /* Effets de bord : Affichage d'une ou plusieurs solutions dans le fichier. */ /*============================================================================*/ void Affiche_Solution_Sans_Symetries_Retournee( FILE* sortie, Surface *surface, Coord *position_croix ); /*============================================================================*/ /* Fonction Ouvrir_Fichier_Solutions : */ /* But : Ouvrir le fichier dans lequel les solutions vont etre */ /* affichees. */ /* Parametres : Un pointeur sur un descripteur de fichier. */ /* Le nom du fichier. */ /* Effets de bord : Ouverture du fichier. */ /* Valeur de retour : 0 si tout s'est bien passe, */ /* Code d'erreur sinon. */ /*============================================================================*/ int Ouvrir_Fichier_Solutions( FILE **f, char *nom_fichier ); /*============================================================================*/ /* Fonction Fermer_Fichier_Solutions : */ /* But : Fermer le fichier dans lequel les solutions ont ete */ /* affichees. */ /* Parametres : Un descripteur de fichier. */ /* Effets de bord : Fermeture du fichier. */ /* Valeur de retour : 0 si tout s'est bien passe, */ /* Code d'erreur sinon. */ /*============================================================================*/ int Fermer_Fichier_Solutions( FILE *f ); /******************************************************************************/ /* pavage.h */ /******************************************************************************/ /*============================================================================*/ /* Fonction Pavage : */ /* But : Placer la croix dans les positions determinees par les */ /* eventuelles symetries. */ /* Parametres : Un pointeur sur les descripteur du fichier de sortie. */ /* La surface a remplir. */ /* Les pieces. */ /* Effets de bord : Appels a la fonction Pavage_Rec. */ /*============================================================================*/ void Pavage (FILE* sortie, Surface *surface, Pieces piece); /*============================================================================*/ /* Fonction Pavage_Rec : */ /* But : Placer les autres pieces dans la surface. Si elles sont */ /* toutes placees, on appele la fonction d'affichage. */ /* Parametres : Un pointeur sur les descripteur du fichier de sortie. */ /* La surface a remplir. */ /* Les pieces. */ /* Un pointeur sue le nombre de pieces deja placees. */ /* La position de la croix ( pour els affichages ). */ /* Les coordonnees de la position a partir de laquelle */ /* il faut chercher une case libre. */ /* Effets de bord : Appels a une fonction d'affichage. */ /*============================================================================*/ void Pavage_Rec (FILE* sortie, Surface *surface, Pieces piece, int *nb_pieces_placees, Coord *position_croix, int colonne, int ligne); /*============================================================================*/ /* Fonction Surface_Close : */ /* But : Recherche des espaces clos. */ /* Parametres : La surface. */ /* Un pointeur sur la piece actuelle. */ /* La position de celle-ci. */ /* Effets de bord : Appels a la fonction Taille_Clos. */ /* Valeur de retour : POSSIBLE ou IMPOSSIBLE selon si on a detecter un espace */ /* clos. */ /*============================================================================*/ int Surface_Close( Surface *surface, Soeur *soeur, int lig_piece, int col_piece ); /*============================================================================*/ /* Fonction Taille_Clos : */ /* But : Recherche des espaces clos. */ /* Parametres : La position de depart. */ /* La figure a parcourir. */ /* Un pointeur sur int pour incrementer la taille de */ /* l'espace actuel. */ /* La valeur de ligne*C+colonne. */ /* Les dimentions de la figure. */ /* Effets de bord : Appels recursifs. */ /* Valeur de retour : Neant. */ /*============================================================================*/ void Taille_Clos( int ligne, int colonne, int *clos, int *taille, int index, int L, int C ); /******************************************************************************/ /* main.h */ /******************************************************************************/ /*============================================================================*/ /* Fonction Usage : */ /* But : Affiche sur stderr la ligne d'usage. */ /* Parametres : Un pointeur sur les arguments. */ /* Effets de bord : Neant. */ /*============================================================================*/ void Usage( char **argv ); /*============================================================================*/ /* Fonction Arguments : */ /* But : Parser la ligne de commande. */ /* Parametres : Le nombres d'arguments. */ /* Les agruments. */ /* Un pointeur sur int pour savoir si on veut une seule */ /* solution. */ /* Un autre pour savoir si on veut les symetries. */ /* Deux pointeurs pour les noms de fichier. */ /* Effets de bord : Neant. */ /* Valeur de retour : 0 si tout s'est bien passe, */ /* Code d'erreur sinon. */ /*============================================================================*/ int Arguments( int argc, char **argv, Options *options ); /******************************************************************************/ /* symetries.c */ /******************************************************************************/ /*============================================================================*/ /* Fonction Recherche_Symetries : */ /* But : Recherche des symetries. */ /* Parametres : La surface. */ /* Effets de bord : Initialisation de certains champs de surface. */ /* Valeur de retour : Neant. */ /*============================================================================*/ void Recherche_Symetries( Surface *surface ) { int i, j; /* Indices de boucles; */ int *grille=surface->Grille; /* Grille. */ int L=surface->NbColonnes; /* Dimension. */ int H=surface->NbLignes; /* Dimension. */ /*----------------------------------------------------------------------------*/ /* Initialisation des symetries : */ /*----------------------------------------------------------------------------*/ surface->H = 1; surface->V = 1; surface->D1 = 0; surface->D2 = 0; /*----------------------------------------------------------------------------*/ /* Symetrie horizontale : */ /*----------------------------------------------------------------------------*/ for (i=0; surface->H && iH = 0; break; } /*----------------------------------------------------------------------------*/ /* Symetrie verticale : */ /*----------------------------------------------------------------------------*/ for (j=0; surface->V && jV = 0; break; } /*----------------------------------------------------------------------------*/ /* Symetries diagonales : */ /*----------------------------------------------------------------------------*/ if ( H != L ) /* Il n'a pas de sym D* */ return; /*----------------------------------------------------------------------------*/ /* On les suppose vraies : */ /*----------------------------------------------------------------------------*/ surface->D1 = 1; surface->D2 = 1; /*----------------------------------------------------------------------------*/ /* Symetrie Diagonale1 : */ /*----------------------------------------------------------------------------*/ for (i=0; surface->D1 && iD1 = 0; break; } /*----------------------------------------------------------------------------*/ /* Symetrie */ /*----------------------------------------------------------------------------*/ for (i=0; surface->D2 && iD2 = 0; break; } } /******************************************************************************/ /* pieces.c */ /******************************************************************************/ /*============================================================================*/ /* Fonction Creation_Pieces : */ /* But : Creer la structure des pieces. */ /* Parametres : Aucuns */ /* Effets de bord : Creation de la structure. */ /* Valeur de retour : L'adresse de la structure. */ /*============================================================================*/ Pieces *Creation_Pieces(void) { static Pieces pieces = /* Pieces a initialiser. */ { { 'X', 1, 0, { { -1, 1, 2, { {-1, 1}, { 0, 2}, { 0, 1}, { 1, 1} }, 16, { {-2, 1}, {-2, 2}, {-1, 2}, {-1, 3}, { 0, 3}, { 1, 0}, { 1, 2}, { 1, 3}, { 2, 0}, { 2, 1}, { 2, 2}, {-1, -1}, {-2, 0}, { 1, -1}, {-1, 0}, { 0, -1} } } } }, { 'I', 2, 0, { { 0, 4, 0, { { 1, 0}, { 2, 0}, { 3, 0}, { 4, 0} }, 8, { {-1, 1}, { 0, 1}, { 1, 1}, { 2, 1}, { 3, 1}, { 4, 1}, { 5, 0}, { 5, 1} } }, { 0, 0, 4, { { 0, 4}, { 0, 3}, { 0, 2}, { 0, 1} }, 12, { {-1, 1}, {-1, 2}, {-1, 3}, {-1, 4}, {-1, 5}, { 0, 5}, { 1, 0}, { 1, 1}, { 1, 2}, { 1, 3}, { 1, 4}, { 1, 5} } } } }, { 'T', 4, 0, { { 0, 2, 2, { { 0, 2}, { 0, 1}, { 1, 1}, { 2, 1} }, 12, { {-1, 1}, {-1, 2}, {-1, 3}, { 0, 3}, { 1, 0}, { 1, 2}, { 1, 3}, { 2, 0}, { 2, 2}, { 3, 0}, { 3, 1}, { 3, 2} } }, { -1, 1, 2, { {-1, 2}, { 0, 2}, { 0, 1}, { 1, 2} }, 12, { {-2, 1}, {-2, 2}, {-2, 3}, {-1, 1}, {-1, 3}, { 0, 3}, { 1, 0}, { 1, 1}, { 1, 3}, { 2, 1}, { 2, 2}, { 2, 3} } }, { 0, 2, 2, { { 1, 0}, { 1, 1}, { 1, 2}, { 2, 0} }, 10, { {-1, 1}, { 0, 1}, { 0, 2}, { 0, 3}, { 1, 3}, { 2, 1}, { 2, 2}, { 2, 3}, { 3, 0}, { 3, 1} } }, { -2, 0, 2, { {-2, 1}, {-1, 1}, { 0, 2}, { 0, 1} }, 10, { {-3, 1}, {-3, 2}, {-2, 2}, {-1, 2}, {-1, 3}, { 0, 3}, { 1, 0}, { 1, 1}, { 1, 2}, { 1, 3} } } } }, { 'E', 4, 0, { { 0, 2, 2, { { 1, 0}, { 1, 1}, { 1, 2}, { 2, 2} }, 11, { {-1, 1}, { 0, 1}, { 0, 2}, { 0, 3}, { 1, 3}, { 2, 0}, { 2, 1}, { 2, 3}, { 3, 1}, { 3, 2}, { 3, 3} } }, { -1, 1, 2, { {-1, 2}, { 0, 2}, { 0, 1}, { 1, 0} }, 11, { {-2, 1}, {-2, 2}, {-2, 3}, {-1, 1}, {-1, 3}, { 0, 3}, { 1, 1}, { 1, 2}, { 1, 3}, { 2, 0}, { 2, 1} } }, { -2, 0, 2, { {-2, 1}, {-2, 2}, {-1, 1}, { 0, 1} }, 10, { {-3, 1}, {-3, 2}, {-3, 3}, {-2, 3}, {-1, 2}, {-1, 3}, { 0, 2}, { 1, 0}, { 1, 1}, { 1, 2} } }, { 0, 2, 2, { { 0, 1}, { 1, 1}, { 2, 1}, { 2, 2} }, 12, { {-1, 1}, {-1, 2}, { 0, 2}, { 1, 0}, { 1, 2}, { 1, 3}, { 2, 0}, { 2, 3}, { 3, 0}, { 3, 1}, { 3, 2}, { 3, 3} } } } }, { 'U', 4, 0, { { 0, 1, 2, { { 0, 2}, { 1, 0}, { 1, 1}, { 1, 2} }, 10, { {-1, 1}, {-1, 2}, {-1, 3}, { 0, 1}, { 0, 3}, { 1, 3}, { 2, 0}, { 2, 1}, { 2, 2}, { 2, 3} } }, { 0, 1, 2, { { 0, 2}, { 0, 1}, { 1, 0}, { 1, 2} }, 10, { {-1, 1}, {-1, 2}, {-1, 3}, { 0, 3}, { 1, 1}, { 1, 3}, { 2, 0}, { 2, 1}, { 2, 2}, { 2, 3} } }, { 0, 2, 1, { { 0, 1}, { 1, 1}, { 2, 0}, { 2, 1} }, 9, { {-1, 1}, {-1, 2}, { 0, 2}, { 1, 0}, { 1, 2}, { 2, 2}, { 3, 0}, { 3, 1}, { 3, 2} } }, { 0, 2, 1, { { 0, 1}, { 1, 0}, { 2, 0}, { 2, 1} }, 9, { {-1, 1}, {-1, 2}, { 0, 2}, { 1, 1}, { 1, 2}, { 2, 2}, { 3, 0}, { 3, 1}, { 3, 2} } } } }, { 'V', 4, 0, { { 0, 2, 2, { { 1, 0}, { 2, 0}, { 2, 1}, { 2, 2} }, 10, { {-1, 1}, { 0, 1}, { 1, 1}, { 1, 2}, { 1, 3}, { 2, 3}, { 3, 0}, { 3, 1}, { 3, 2}, { 3, 3} } }, { -2, 0, 2, { {-2, 2}, {-1, 2}, { 0, 2}, { 0, 1} }, 12, { {-3, 1}, {-3, 2}, {-3, 3}, {-2, 1}, {-2, 3}, {-1, 1}, {-1, 3}, { 0, 3}, { 1, 0}, { 1, 1}, { 1, 2}, { 1, 3} } }, { 0, 2, 2, { { 0, 2}, { 0, 1}, { 1, 0}, { 2, 0} }, 10, { {-1, 1}, {-1, 2}, {-1, 3}, { 0, 3}, { 1, 1}, { 1, 2}, { 1, 3}, { 2, 1}, { 3, 0}, { 3, 1} } }, { 0, 2, 2, { { 0, 2}, { 0, 1}, { 1, 2}, { 2, 2} }, 12, { {-1, 1}, {-1, 2}, {-1, 3}, { 0, 3}, { 1, 0}, { 1, 1}, { 1, 3}, { 2, 1}, { 2, 3}, { 3, 1}, { 3, 2}, { 3, 3} } } } }, { 'W', 4, 0, { { 0, 2, 2, { { 1, 0}, { 1, 1}, { 2, 1}, { 2, 2} }, 11, { {-1, 1}, { 0, 1}, { 0, 2}, { 1, 2}, { 1, 3}, { 2, 0}, { 2, 3}, { 3, 0}, { 3, 1}, { 3, 2}, { 3, 3} } }, { -2, 0, 2, { {-2, 2}, {-1, 1}, {-1, 2}, { 0, 1} }, 11, { {-3, 1}, {-3, 2}, {-3, 3}, {-2, 1}, {-2, 3}, {-1, 3}, { 0, 2}, { 0, 3}, { 1, 0}, { 1, 1}, { 1, 2} } }, { -1, 1, 2, { {-1, 1}, {-1, 2}, { 0, 1}, { 1, 0} }, 10, { {-2, 1}, {-2, 2}, {-2, 3}, {-1, 3}, { 0, 2}, { 0, 3}, { 1, 1}, { 1, 2}, { 2, 0}, { 2, 1} } }, { 0, 2, 2, { { 0, 1}, { 1, 1}, { 1, 2}, { 2, 2} }, 12, { {-1, 1}, {-1, 2}, { 0, 2}, { 0, 3}, { 1, 0}, { 1, 3}, { 2, 0}, { 2, 1}, { 2, 3}, { 3, 1}, { 3, 2}, { 3, 3} } } } }, { 'L', 8, 0, { { 0, 3, 1, { { 0, 1}, { 1, 1}, { 2, 1}, { 3, 1} }, 12, { {-1, 1}, {-1, 2}, { 0, 2}, { 1, 0}, { 1, 2}, { 2, 0}, { 2, 2}, { 3, 0}, { 3, 2}, { 4, 0}, { 4, 1}, { 4, 2} } }, { 0, 3, 1, { { 0, 1}, { 1, 0}, { 2, 0}, { 3, 0} }, 9, { {-1, 1}, {-1, 2}, { 0, 2}, { 1, 1}, { 1, 2}, { 2, 1}, { 3, 1}, { 4, 0}, { 4, 1} } }, { -3, 0, 1, { {-3, 1}, {-2, 1}, {-1, 1}, { 0, 1} }, 9, { {-4, 1}, {-4, 2}, {-3, 2}, {-2, 2}, {-1, 2}, { 0, 2}, { 1, 0}, { 1, 1}, { 1, 2} } }, { 0, 3, 1, { { 1, 0}, { 2, 0}, { 3, 0}, { 3, 1} }, 9, { {-1, 1}, { 0, 1}, { 1, 1}, { 2, 1}, { 2, 2}, { 3, 2}, { 4, 0}, { 4, 1}, { 4, 2} } }, { 0, 1, 3, { { 0, 3}, { 0, 2}, { 0, 1}, { 1, 0} }, 11, { {-1, 1}, {-1, 2}, {-1, 3}, {-1, 4}, { 0, 4}, { 1, 1}, { 1, 2}, { 1, 3}, { 1, 4}, { 2, 0}, { 2, 1} } }, { 0, 1, 3, { { 1, 0}, { 1, 1}, { 1, 2}, { 1, 3} }, 11, { {-1, 1}, { 0, 1}, { 0, 2}, { 0, 3}, { 0, 4}, { 1, 4}, { 2, 0}, { 2, 1}, { 2, 2}, { 2, 3}, { 2, 4} } }, { 0, 1, 3, { { 0, 3}, { 0, 2}, { 0, 1}, { 1, 3} }, 12, { {-1, 1}, {-1, 2}, {-1, 3}, {-1, 4}, { 0, 4}, { 1, 0}, { 1, 1}, { 1, 2}, { 1, 4}, { 2, 2}, { 2, 3}, { 2, 4} } }, { -1, 0, 3, { {-1, 3}, { 0, 3}, { 0, 2}, { 0, 1} }, 12, { {-2, 2}, {-2, 3}, {-2, 4}, {-1, 1}, {-1, 2}, {-1, 4}, { 0, 4}, { 1, 0}, { 1, 1}, { 1, 2}, { 1, 3}, { 1, 4} } } } }, { 'Y', 8, 0, { { 0, 1, 3, { { 0, 3}, { 0, 2}, { 0, 1}, { 1, 1} }, 12, { {-1, 1}, {-1, 2}, {-1, 3}, {-1, 4}, { 0, 4}, { 1, 0}, { 1, 2}, { 1, 3}, { 1, 4}, { 2, 0}, { 2, 1}, { 2, 2} } }, { -1, 0, 3, { {-1, 1}, { 0, 3}, { 0, 2}, { 0, 1} }, 11, { {-2, 1}, {-2, 2}, {-1, 2}, {-1, 3}, {-1, 4}, { 0, 4}, { 1, 0}, { 1, 1}, { 1, 2}, { 1, 3}, { 1, 4} } }, { 0, 1, 3, { { 0, 3}, { 0, 2}, { 0, 1}, { 1, 2} }, 12, { {-1, 1}, {-1, 2}, {-1, 3}, {-1, 4}, { 0, 4}, { 1, 0}, { 1, 1}, { 1, 3}, { 1, 4}, { 2, 1}, { 2, 2}, { 2, 3} } }, { -1, 0, 3, { {-1, 2}, { 0, 3}, { 0, 2}, { 0, 1} }, 12, { {-2, 1}, {-2, 2}, {-2, 3}, {-1, 1}, {-1, 3}, {-1, 4}, { 0, 4}, { 1, 0}, { 1, 1}, { 1, 2}, { 1, 3}, { 1, 4} } }, { -1, 2, 1, { {-1, 1}, { 0, 1}, { 1, 1}, { 2, 1} }, 11, { {-2, 1}, {-2, 2}, {-1, 2}, { 0, 2}, { 1, 0}, { 1, 2}, { 2, 0}, { 2, 2}, { 3, 0}, { 3, 1}, { 3, 2} } }, { -2, 1, 1, { {-2, 1}, {-1, 1}, { 0, 1}, { 1, 1} }, 10, { {-3, 1}, {-3, 2}, {-2, 2}, {-1, 2}, { 0, 2}, { 1, 0}, { 1, 2}, { 2, 0}, { 2, 1}, { 2, 2} } }, { 0, 3, 1, { { 1, 0}, { 1, 1}, { 2, 0}, { 3, 0} }, 9, { {-1, 1}, { 0, 1}, { 0, 2}, { 1, 2}, { 2, 1}, { 2, 2}, { 3, 1}, { 4, 0}, { 4, 1} } }, { 0, 3, 1, { { 1, 0}, { 2, 0}, { 2, 1}, { 3, 0} }, 9, { {-1, 1}, { 0, 1}, { 1, 1}, { 1, 2}, { 2, 2}, { 3, 1}, { 3, 2}, { 4, 0}, { 4, 1} } } } }, { 'F', 8, 0, { { 0, 2, 2, { { 0, 1}, { 1, 1}, { 1, 2}, { 2, 1} }, 12, { {-1, 1}, {-1, 2}, { 0, 2}, { 0, 3}, { 1, 0}, { 1, 3}, { 2, 0}, { 2, 2}, { 2, 3}, { 3, 0}, { 3, 1}, { 3, 2} } }, { -2, 0, 2, { {-2, 1}, {-1, 1}, {-1, 2}, { 0, 1} }, 10, { {-3, 1}, {-3, 2}, {-2, 2}, {-2, 3}, {-1, 3}, { 0, 2}, { 0, 3}, { 1, 0}, { 1, 1}, { 1, 2} } }, { -1, 1, 2, { {-1, 1}, {-1, 2}, { 0, 1}, { 1, 1} }, 11, { {-2, 1}, {-2, 2}, {-2, 3}, {-1, 3}, { 0, 2}, { 0, 3}, { 1, 0}, { 1, 2}, { 2, 0}, { 2, 1}, { 2, 2} } }, { -1, 1, 2, { {-1, 1}, { 0, 1}, { 1, 1}, { 1, 2} }, 11, { {-2, 1}, {-2, 2}, {-1, 2}, { 0, 2}, { 0, 3}, { 1, 0}, { 1, 3}, { 2, 0}, { 2, 1}, { 2, 2}, { 2, 3} } }, { 0, 2, 2, { { 1, 0}, { 1, 1}, { 1, 2}, { 2, 1} }, 11, { {-1, 1}, { 0, 1}, { 0, 2}, { 0, 3}, { 1, 3}, { 2, 0}, { 2, 2}, { 2, 3}, { 3, 0}, { 3, 1}, { 3, 2} } }, { -1, 1, 2, { {-1, 1}, { 0, 2}, { 0, 1}, { 1, 0} }, 10, { {-2, 1}, {-2, 2}, {-1, 2}, {-1, 3}, { 0, 3}, { 1, 1}, { 1, 2}, { 1, 3}, { 2, 0}, { 2, 1} } }, { -1, 1, 2, { {-1, 2}, { 0, 2}, { 0, 1}, { 1, 1} }, 12, { {-2, 1}, {-2, 2}, {-2, 3}, {-1, 1}, {-1, 3}, { 0, 3}, { 1, 0}, { 1, 2}, { 1, 3}, { 2, 0}, { 2, 1}, { 2, 2} } }, { -1, 1, 2, { {-1, 1}, { 0, 2}, { 0, 1}, { 1, 2} }, 11, { {-2, 1}, {-2, 2}, {-1, 2}, {-1, 3}, { 0, 3}, { 1, 0}, { 1, 1}, { 1, 3}, { 2, 1}, { 2, 2}, { 2, 3} } } } }, { 'N', 8, 0, { { 0, 3, 1, { { 1, 0}, { 1, 1}, { 2, 1}, { 3, 1} }, 11, { {-1, 1}, { 0, 1}, { 0, 2}, { 1, 2}, { 2, 0}, { 2, 2}, { 3, 0}, { 3, 2}, { 4, 0}, { 4, 1}, { 4, 2} } }, { -2, 1, 1, { {-2, 1}, {-1, 1}, { 0, 1}, { 1, 0} }, 9, { {-3, 1}, {-3, 2}, {-2, 2}, {-1, 2}, { 0, 2}, { 1, 1}, { 1, 2}, { 2, 0}, { 2, 1} } }, { -1, 2, 1, { {-1, 1}, { 0, 1}, { 1, 0}, { 2, 0} }, 9, { {-2, 1}, {-2, 2}, {-1, 2}, { 0, 2}, { 1, 1}, { 1, 2}, { 2, 1}, { 3, 0}, { 3, 1} } }, { 0, 3, 1, { { 1, 0}, { 2, 0}, { 2, 1}, { 3, 1} }, 10, { {-1, 1}, { 0, 1}, { 1, 1}, { 1, 2}, { 2, 2}, { 3, 0}, { 3, 2}, { 4, 0}, { 4, 1}, { 4, 2} } }, { -1, 0, 3, { {-1, 2}, {-1, 3}, { 0, 2}, { 0, 1} }, 12, { {-2, 1}, {-2, 2}, {-2, 3}, {-2, 4}, {-1, 1}, {-1, 4}, { 0, 3}, { 0, 4}, { 1, 0}, { 1, 1}, { 1, 2}, { 1, 3} } }, { 0, 1, 3, { { 0, 2}, { 0, 1}, { 1, 2}, { 1, 3} }, 12, { {-1, 1}, {-1, 2}, {-1, 3}, { 0, 3}, { 0, 4}, { 1, 0}, { 1, 1}, { 1, 4}, { 2, 1}, { 2, 2}, { 2, 3}, { 2, 4} } }, { 0, 1, 3, { { 0, 1}, { 1, 1}, { 1, 2}, { 1, 3} }, 12, { {-1, 1}, {-1, 2}, { 0, 2}, { 0, 3}, { 0, 4}, { 1, 0}, { 1, 4}, { 2, 0}, { 2, 1}, { 2, 2}, { 2, 3}, { 2, 4} } }, { -1, 0, 3, { {-1, 1}, {-1, 2}, {-1, 3}, { 0, 1} }, 11, { {-2, 1}, {-2, 2}, {-2, 3}, {-2, 4}, {-1, 4}, { 0, 2}, { 0, 3}, { 0, 4}, { 1, 0}, { 1, 1}, { 1, 2} } } } }, { 'P', 8, 0, { { 0, 2, 1, { { 0, 1}, { 1, 0}, { 1, 1}, { 2, 0} }, 8, { {-1, 1}, {-1, 2}, { 0, 2}, { 1, 2}, { 2, 1}, { 2, 2}, { 3, 0}, { 3, 1} } }, { 0, 2, 1, { { 1, 0}, { 1, 1}, { 2, 0}, { 2, 1} }, 8, { {-1, 1}, { 0, 1}, { 0, 2}, { 1, 2}, { 2, 2}, { 3, 0}, { 3, 1}, { 3, 2} } }, { 0, 2, 1, { { 0, 1}, { 1, 0}, { 1, 1}, { 2, 1} }, 9, { {-1, 1}, {-1, 2}, { 0, 2}, { 1, 2}, { 2, 0}, { 2, 2}, { 3, 0}, { 3, 1}, { 3, 2} } }, { -1, 1, 1, { {-1, 1}, { 0, 1}, { 1, 0}, { 1, 1} }, 8, { {-2, 1}, {-2, 2}, {-1, 2}, { 0, 2}, { 1, 2}, { 2, 0}, { 2, 1}, { 2, 2} } }, { 0, 1, 2, { { 0, 2}, { 0, 1}, { 1, 1}, { 1, 2} }, 10, { {-1, 1}, {-1, 2}, {-1, 3}, { 0, 3}, { 1, 0}, { 1, 3}, { 2, 0}, { 2, 1}, { 2, 2}, { 2, 3} } }, { -1, 0, 2, { {-1, 1}, {-1, 2}, { 0, 2}, { 0, 1} }, 9, { {-2, 1}, {-2, 2}, {-2, 3}, {-1, 3}, { 0, 3}, { 1, 0}, { 1, 1}, { 1, 2}, { 1, 3} } }, { 0, 1, 2, { { 0, 2}, { 0, 1}, { 1, 0}, { 1, 1} }, 9, { {-1, 1}, {-1, 2}, {-1, 3}, { 0, 3}, { 1, 2}, { 1, 3}, { 2, 0}, { 2, 1}, { 2, 2} } }, { 0, 1, 2, { { 0, 1}, { 1, 0}, { 1, 1}, { 1, 2} }, 9, { {-1, 1}, {-1, 2}, { 0, 2}, { 0, 3}, { 1, 3}, { 2, 0}, { 2, 1}, { 2, 2}, { 2, 3} } } } } }; return( &pieces ); } /******************************************************************************/ /* interface.c */ /******************************************************************************/ /*============================================================================*/ /* Fonction Lecture : */ /* But : Lire dans un fichier la figure a paver. */ /* Parametres : Le nom du fichier. */ /* La surface a remplir. */ /* Un pointeur sur int pour dire si elle a ete retournee. */ /* Effets de bord : Initialisation de la surface. */ /* Valeur de retour : 0 si tout s'est bien passe, */ /* Code d'erreur sinon. */ /*============================================================================*/ int Lecture( char *nom_fichier, Surface *surface, int *retournee ) { FILE *fichier; /* Descripteur de fichier. */ int nb_colonnes; /* Largeur de la surface a paver. */ int nb_lignes; /* Hauteur de la surface a paver. */ int c; /* Caractere lu. */ int colonne; /* Indice de colonne. */ int ligne; /* Indice de ligne. */ /*----------------------------------------------------------------------------*/ /* Ouverture du fichier de donnees : */ /*----------------------------------------------------------------------------*/ if (nom_fichier) { if ( !(fichier = fopen(nom_fichier, "r")) ) { fprintf(stderr, "Ouverture du fichier %s impossible.\n", nom_fichier); return (OPEN_F_ERR); } } else fichier = stdin; /*----------------------------------------------------------------------------*/ /* Lecture des dimensions de la surface a paver : */ /*----------------------------------------------------------------------------*/ if ( (fscanf(fichier, "%d %d ", &nb_lignes, &nb_colonnes) != 2) ) { fprintf(stderr, "Lecture des dimensions impossibles.\n"); return (LECTUR_ERR); } if ( nb_lignes <= 0 || nb_colonnes <= 0 || nb_lignes * nb_colonnes < PENTO * NB_FAMILLES ) { fprintf(stderr, "Dimensions erronees.\n"); return (DIM_ERR); } /*----------------------------------------------------------------------------*/ /* Doit-on retourner la surface ? */ /*----------------------------------------------------------------------------*/ if( nb_colonnes > nb_lignes ) { *retournee = 1; surface->NbColonnes = nb_lignes; surface->NbLignes = nb_colonnes; } else { *retournee = 0; surface->NbColonnes = nb_colonnes; surface->NbLignes = nb_lignes; } /*----------------------------------------------------------------------------*/ /* Allocation et lecture de la surface a paver : */ /*----------------------------------------------------------------------------*/ if ( !( surface->Grille = (int*) calloc( nb_colonnes *nb_lignes, sizeof(int) ) ) || !( surface->clos = (int*) calloc( nb_colonnes *nb_lignes, sizeof(int) ) ) || !( surface->buf = (char*)calloc((nb_colonnes+1)*nb_lignes+1, sizeof(char) ) ) ) { fprintf(stderr, "Impossible d'allouer de la memoire.\n"); return (ALLOC_ERR); } colonne = 0; ligne = 0; while ( ((c = fgetc(fichier)) != EOF) && (ligne < nb_lignes) && (colonne <= nb_colonnes) ) if (c == '\n') { ligne ++; colonne = 0; } else if ( c == LIBRE || c == OCCUPE ) { if( *retournee ) surface->Grille[colonne * nb_lignes + ligne] = c; else surface->Grille[ligne * nb_colonnes + colonne] = c; colonne ++; } else { fprintf(stderr, "Format des donnees incorrect.\n"); return (FORMAT_ERR); } /*----------------------------------------------------------------------------*/ /* Fermeture du fichier : */ /*----------------------------------------------------------------------------*/ if( fichier != stdin ) if( fclose( fichier ) >0 ) return( FCLOSE_ERR ); surface->nb_sol = 0; return 0; } /*============================================================================*/ /* Fonction Affiche_Solution : */ /* But : Affiche une solution dans un fichier. */ /* Parametres : Le fichier. */ /* La surface a afficher. */ /* La position de la croix. */ /* Effets de bord : Affichage d'une ou plusieurs solutions dans le fichier. */ /*============================================================================*/ void Affiche_Solution( FILE* sortie, Surface *surface, Coord *position_croix ) { static int i, j; /* Indices dans la surface. */ static int C; /* Dimensions de la surface. */ static int L; /* Dimensions de la surface. */ static char *buf = NULL; /* Surface a afficher. */ static int taille_buf; /* Taille de la surface a afficher. */ /*----------------------------------------------------------------------------*/ /* Initialisations : */ /*----------------------------------------------------------------------------*/ C = surface->NbColonnes; L = surface->NbLignes; if ( !buf ) { buf = surface->buf; taille_buf = ((C+1)*L+1)*sizeof(char); buf[(C+1)*L] = '\n'; for (i=0; inb_sol) ++; for (i=0; iGrille[i*C + j]; fwrite( buf, sizeof(char), taille_buf, sortie ); /*----------------------------------------------------------------------------*/ /* Symetrie horizontale */ /*----------------------------------------------------------------------------*/ if (surface->H && position_croix->l+1 != L/2 )/* La croix n'est pas sur l'axe de sym*/ { (surface->nb_sol) ++; for (i=0; iGrille[i*C + j]; fwrite( buf, sizeof(char), taille_buf, sortie ); } /*----------------------------------------------------------------------------*/ /* Symetrie verticale */ /*----------------------------------------------------------------------------*/ if (surface->V && position_croix->c != C/2 ) /* La croix n'est pas sur l'axe de sym*/ { (surface->nb_sol) ++; for (i=0; iGrille[i*C + j]; fwrite( buf, sizeof(char), taille_buf, sortie ); } /*----------------------------------------------------------------------------*/ /* Symetrie premiere diagonale */ /*----------------------------------------------------------------------------*/ if (surface->D1 && position_croix->l+1 != position_croix->c) { (surface->nb_sol) ++; for (i=0; iGrille[i*C + j]; fwrite( buf, sizeof(char), taille_buf, sortie ); } /*----------------------------------------------------------------------------*/ /* Symetrie seconde diagonale */ /*----------------------------------------------------------------------------*/ if (surface->D2 && C - position_croix->l != position_croix->c) { (surface->nb_sol) ++; for (i=0; iGrille[i*C + j]; fwrite( buf, sizeof(char), taille_buf, sortie ); } /*----------------------------------------------------------------------------*/ /* Symetrie horizontale + verticale */ /*----------------------------------------------------------------------------*/ if( ( surface->H && surface->V && !surface->D2 && position_croix->l+1 != L/2 && position_croix->c != C/2 ) || ( surface->D1 && surface->D2 && !surface->H && position_croix->l+1 != position_croix->c && C - position_croix->l != position_croix->c ) ) { (surface->nb_sol) ++; for (i=0; iGrille[(L-i-1)*C + C-j-1]; fwrite( buf, sizeof(char), taille_buf, sortie ); } /*----------------------------------------------------------------------------*/ /* Symetrie verticale et premiere diagonale */ /*----------------------------------------------------------------------------*/ if( surface->V && surface->D1 && position_croix->c != C/2 && position_croix->l+1 != position_croix->c ) { (surface->nb_sol) +=3 ; /*----------------------------------------------------------------------*/ /* horizontale + verticale */ /*----------------------------------------------------------------------*/ for (i=0; iGrille[(L-i-1)*C + C-j-1]; fwrite( buf, sizeof(char), taille_buf, sortie ); /*----------------------------------------------------------------------*/ /* horizontale + premiere diagonale */ /*----------------------------------------------------------------------*/ for (i=0; iGrille[j*C + C-i-1]; fwrite( buf, sizeof(char), taille_buf, sortie ); /*----------------------------------------------------------------------*/ /* horizontale + seconde diagonale */ /*----------------------------------------------------------------------*/ for (i=0; iGrille[(L-j-1)*C + i]; fwrite( buf, sizeof(char), taille_buf, sortie ); } return; } /*============================================================================*/ /* Fonction Affiche_Solution_Retournee : */ /* But : Affiche une solution dans un fichier. */ /* Parametres : Le fichier. */ /* La surface a afficher retournee. */ /* La position de la croix. */ /* Effets de bord : Affichage d'une ou plusieurs solutions dans le fichier. */ /*============================================================================*/ void Affiche_Solution_Retournee( FILE* sortie, Surface *surface, Coord *position_croix ) { static int i, j; /* Indices dans la surface. */ static int C; /* Dimensions de la surface. */ static int L; /* Dimensions de la surface. */ static char *buf = NULL; /* Surface a afficher. */ static int taille_buf; /* Taille de la surface a afficher. */ /*----------------------------------------------------------------------------*/ /* Initialisations : */ /*----------------------------------------------------------------------------*/ L = surface->NbColonnes; C = surface->NbLignes; if ( !buf ) { buf = surface->buf; taille_buf = ((C+1)*L+1)*sizeof(char); buf[(C+1)*L] = '\n'; for (i=0; inb_sol) ++; for (i=0; iGrille[i*L + j]; fwrite( buf, sizeof(char), taille_buf, sortie ); /*----------------------------------------------------------------------------*/ /* Symetrie horizontale */ /*----------------------------------------------------------------------------*/ if (surface->H && position_croix->l+1 != C/2 )/* La croix n'est pas sur l'axe de sym*/ { (surface->nb_sol) ++; for (i=0; iGrille[i*L + j]; fwrite( buf, sizeof(char), taille_buf, sortie ); } /*----------------------------------------------------------------------------*/ /* Symetrie verticale */ /*----------------------------------------------------------------------------*/ if (surface->V && position_croix->c != L/2 ) /* La croix n'est pas sur l'axe de sym*/ { (surface->nb_sol) ++; for (i=0; iGrille[i*L + j]; fwrite( buf, sizeof(char), taille_buf, sortie ); } /*----------------------------------------------------------------------------*/ /* Symetrie horizontale + verticale */ /*----------------------------------------------------------------------------*/ if( surface->H && surface->V && position_croix->l+1 != C/2 && position_croix->c != L/2 ) { (surface->nb_sol) ++; for (i=0; iGrille[i*L + j]; fwrite( buf, sizeof(char), taille_buf, sortie ); } return; } /*============================================================================*/ /* Fonction Affiche_Une_Solution : */ /* But : Affiche une solution dans un fichier. */ /* Parametres : Le fichier. */ /* La surface a afficher. */ /* La position de la croix. */ /* Effets de bord : Affichage d'une ou plusieurs solutions dans le fichier. */ /* Ferme le fichier de sortie. */ /* Liberation des structures allouees avec calloc. */ /* Sortie du programme. */ /*============================================================================*/ void Affiche_Une_Solution( FILE* sortie, Surface *surface, Coord *position_croix ) { int i, j; /* Indices dans la surface. */ int C; /* Dimensions de la surface. */ int L; /* Dimensions de la surface. */ char *buf = NULL; /* Surface a afficher. */ int taille_buf; /* Taille de la surface a afficher. */ /*----------------------------------------------------------------------------*/ /* Initialisations : */ /*----------------------------------------------------------------------------*/ C = surface->NbColonnes; L = surface->NbLignes; buf = surface->buf; taille_buf = ((C+1)*L+1)*sizeof(char); buf[(C+1)*L] = '\n'; for (i=0; inb_sol) ++; for (i=0; iGrille[i*C + j]; fwrite( buf, sizeof(char), taille_buf, sortie ); /*----------------------------------------------------------------------------*/ /* On s'en va .... */ /*----------------------------------------------------------------------------*/ Fermer_Fichier_Solutions( sortie ); free( surface->clos ); free( surface->buf ); free( surface->Grille ); exit( 0 ); } /*============================================================================*/ /* Fonction Affiche_Une_Solution_Retournee : */ /* But : Affiche une solution dans un fichier. */ /* Parametres : Le fichier. */ /* La surface a afficher retournee. */ /* La position de la croix. */ /* Effets de bord : Affichage d'une ou plusieurs solutions dans le fichier. */ /* Ferme le fichier de sortie. */ /* Liberation des structures allouees avec calloc. */ /* Sortie du programme. */ /*============================================================================*/ void Affiche_Une_Solution_Retournee( FILE* sortie, Surface *surface, Coord *position_croix ) { int i, j; /* Indices dans la surface. */ int C; /* Dimensions de la surface. */ int L; /* Dimensions de la surface. */ char *buf = NULL; /* Surface a afficher. */ int taille_buf; /* Taille de la surface a afficher. */ /*----------------------------------------------------------------------------*/ /* Initialisations : */ /*----------------------------------------------------------------------------*/ L = surface->NbColonnes; C = surface->NbLignes; buf = surface->buf; taille_buf = ((C+1)*L+1)*sizeof(char); buf[(C+1)*L] = '\n'; for (i=0; inb_sol) ++; for (i=0; iGrille[i*L + j]; fwrite( buf, sizeof(char), taille_buf, sortie ); /*----------------------------------------------------------------------------*/ /* On s'en va .... */ /*----------------------------------------------------------------------------*/ Fermer_Fichier_Solutions( sortie ); free( surface->clos ); free( surface->buf ); free( surface->Grille ); exit( 0 ); } /*============================================================================*/ /* Fonction Affiche_Solution_Sans_Symetries : */ /* But : Affiche une solution dans un fichier. */ /* Parametres : Le fichier. */ /* La surface a afficher. */ /* La position de la croix. */ /* Effets de bord : Affichage d'une ou plusieurs solutions dans le fichier. */ /*============================================================================*/ void Affiche_Solution_Sans_Symetries( FILE *sortie, Surface *surface, Coord *position_croix ) { int i, j; /* Indices dans la surface. */ int C; /* Dimensions de la surface. */ int L; /* Dimensions de la surface. */ char *buf = NULL; /* Surface a afficher. */ int taille_buf; /* Taille de la surface a afficher. */ /*----------------------------------------------------------------------------*/ /* Initialisations : */ /*----------------------------------------------------------------------------*/ C = surface->NbColonnes; L = surface->NbLignes; buf = surface->buf; taille_buf = ((C+1)*L+1)*sizeof(char); buf[(C+1)*L] = '\n'; for (i=0; inb_sol) ++; for (i=0; iGrille[i*C + j]; fwrite( buf, sizeof(char), taille_buf, sortie ); return; } /*============================================================================*/ /* Fonction Affiche_Solution_Sans_Symetries_Retournee : */ /* But : Affiche une solution dans un fichier. */ /* Parametres : Le fichier. */ /* La surface a afficher retournee. */ /* La position de la croix. */ /* Effets de bord : Affichage d'une ou plusieurs solutions dans le fichier. */ /*============================================================================*/ void Affiche_Solution_Sans_Symetries_Retournee( FILE* sortie, Surface *surface, Coord *position_croix ) { int i, j; /* Indices dans la surface. */ int C; /* Dimensions de la surface. */ int L; /* Dimensions de la surface. */ char *buf = NULL; /* Surface a afficher. */ int taille_buf; /* Taille de la surface a afficher. */ /*----------------------------------------------------------------------------*/ /* Initialisations : */ /*----------------------------------------------------------------------------*/ L = surface->NbColonnes; C = surface->NbLignes; buf = surface->buf; taille_buf = ((C+1)*L+1)*sizeof(char); buf[(C+1)*L] = '\n'; for (i=0; inb_sol) ++; for (i=0; iGrille[i*L + j]; fwrite( buf, sizeof(char), taille_buf, sortie ); return; } /*============================================================================*/ /* Fonction Ouvrir_Fichier_Solutions : */ /* But : Ouvrir le fichier dans lequel les solutions vont etre */ /* affichees. */ /* Parametres : Un pointeur sur un descripteur de fichier. */ /* Le nom du fichier. */ /* Effets de bord : Ouverture du fichier. */ /* Valeur de retour : 0 si tout s'est bien passe, */ /* Code d'erreur sinon. */ /*============================================================================*/ int Ouvrir_Fichier_Solutions( FILE **f, char *nom_fichier ) { if (nom_fichier) { if( !(*f= fopen( nom_fichier, "w" ) ) ) { fprintf(stderr, "Ouverture du fichier %s impossible.\n", nom_fichier); return (OPEN_F_ERR); } } else *f = stdout; return 0; } /*============================================================================*/ /* Fonction Fermer_Fichier_Solutions : */ /* But : Fermer le fichier dans lequel les solutions ont ete */ /* affichees. */ /* Parametres : Un descripteur de fichier. */ /* Effets de bord : Fermeture du fichier. */ /* Valeur de retour : 0 si tout s'est bien passe, */ /* Code d'erreur sinon. */ /*============================================================================*/ int Fermer_Fichier_Solutions (FILE *f) { if( f != stdout ) if( fclose( f ) == EOF ) return( FCLOSE_ERR ); return 0; } /******************************************************************************/ /* pavage.c */ /******************************************************************************/ /*============================================================================*/ /* Fonction Pavage : */ /* But : Placer la croix dans les positions determinees par les */ /* eventuelles symetries. */ /* Parametres : Un pointeur sur les descripteur du fichier de sortie. */ /* La surface a remplir. */ /* Les pieces. */ /* Effets de bord : Appels a la fonction Pavage_Rec. */ /*============================================================================*/ void Pavage( FILE* sortie, Surface *surface, Pieces piece ) { int ligne; /* Ligne dans la surface a paver. */ int colonne; /* Colonne dans la surface a paver. */ int lettre; /* Lettre correspondant a la piece. */ Coord *position; /* Racourci pour la position relative.*/ int L = surface->NbLignes; /* Hauteur de la surface a paver. */ int C = surface->NbColonnes; /* Largeur de la surface a paver. */ int D1 = surface->D1; /* Racourci pour la 1re diagonale. */ int max_ligne; /* Zone d'evolution de la croix. */ int max_colonne; /* Zone d'evolution de la croix. */ int nb_pieces_placees; /* Nombre de pieces placees ici. */ Coord position_croix; /* Pour l'affichage des symetries. */ /*----------------------------------------------------------------------------*/ /* Initialisations : */ /*----------------------------------------------------------------------------*/ nb_pieces_placees = 0; piece[0].Place = 1; max_ligne = (surface->H?(L+1)/2-1:L) ; max_colonne = (surface->V?(C+1)/2:C) ; /*----------------------------------------------------------------------------*/ /* Recherche de la premiere place libre pour placer la coix : */ /*----------------------------------------------------------------------------*/ for (ligne=0; ligne< max_ligne; ligne++) for (colonne = (D1?ligne+1:0); colonne < max_colonne; colonne ++) if (surface->Grille[ligne *C + colonne ] == LIBRE ) { /*----------------------------------------------------------------------*/ /* On a trouve une place libre, peut-on y placer cette piece ? */ /*----------------------------------------------------------------------*/ position = piece[0].Formes[0].Position; if ( DIMENSIONS_OK(0,0) && PLACABLE ) { /*----------------------------------------------------------------*/ /* Placer la piece : */ /*----------------------------------------------------------------*/ lettre = piece[0].Lettre; PLACER(lettre); nb_pieces_placees ++; position_croix.c = colonne; position_croix.l = ligne; /*----------------------------------------------------------------*/ /* Si on a pas delimite de surface close, on continue a paver : */ /*----------------------------------------------------------------*/ if( Surface_Close( surface, piece[0].Formes, colonne, ligne ) != IMPOSSIBLE ) Pavage_Rec( sortie, surface, piece, &nb_pieces_placees, &position_croix, 0, 0 ); /*----------------------------------------------------------------*/ /* On enleve la piece qui a ete placee : */ /*----------------------------------------------------------------*/ ENLEVER(colonne,ligne); nb_pieces_placees --; } } return; } /*============================================================================*/ /* Fonction Pavage_Rec : */ /* But : Placer les autres pieces dans la surface. Si elles sont */ /* toutes placees, on appele la fonction d'affichage. */ /* Parametres : Un pointeur sur les descripteur du fichier de sortie. */ /* La surface a remplir. */ /* Les pieces. */ /* Un pointeur sue le nombre de pieces deja placees. */ /* La position de la croix ( pour els affichages ). */ /* Les coordonnees de la position a partir de laquelle */ /* il faut chercher une case libre. */ /* Effets de bord : Appels a une fonction d'affichage. */ /*============================================================================*/ void Pavage_Rec (FILE* sortie, Surface *surface, Pieces piece, int *nb_pieces_placees, Coord *position_croix, int colonne, int ligne) { int index_piece; /* No de la piece a placer. */ int index_soeur; /* Rotation possible de la piece. */ Coord *position; /* Racourci pour la position relative.*/ static int lettre; /* Lettre correspondant a la piece. */ static int C; /* Largeur de la surface a paver. */ static int L; /* Hauteur de la surface a paver. */ /*----------------------------------------------------------------------------*/ /* Si toutes les pieces sont placees, il faut afficher : */ /*----------------------------------------------------------------------------*/ if (*nb_pieces_placees == NB_FAMILLES) { (surface->Affichage)(sortie, surface, position_croix); return; } /*----------------------------------------------------------------------------*/ /* Initialisations : */ /*----------------------------------------------------------------------------*/ C = surface->NbColonnes; L = surface->NbLignes; /*----------------------------------------------------------------------------*/ /* Recherche de la premiere place libre : */ /*----------------------------------------------------------------------------*/ while ( surface->Grille[ligne *C + colonne ] != LIBRE ) if ( ++colonne == C ) { ligne ++; colonne = 0; } /*----------------------------------------------------------------------------*/ /* Recherche des pieces pouvant s'y placer : */ /*----------------------------------------------------------------------------*/ for (index_piece=1; index_pieceNbColonnes; L = surface->NbLignes; clos = surface->clos; memcpy( surface->clos, surface->Grille, L*C*sizeof( int ) ); /*----------------------------------------------------------------------------*/ /* Recherche de la premiere place libre : */ /*----------------------------------------------------------------------------*/ for( i=0; iNbBords; i++ ) { colonne = col_piece + soeur->Bords[i].c; ligne = lig_piece + soeur->Bords[i].l; if( colonne>=0 && colonne=0 && ligne=1 && clos[index-1] == LIBRE) Taille_Clos (colonne-1, ligne, clos, taille, index-1, C, L); if ( colonne =1 && clos[index-C] == LIBRE) Taille_Clos (colonne, ligne-1, clos, taille, index-C, C, L); if ( ligne unique = 0; options->symetries = 1; options->nombre = 0; options->nom_f_entree = 0; options->nom_f_sortie = 0; option_o_lue = 0; /*----------------------------------------------------------------------------*/ /* Lecture des arguments : */ /*----------------------------------------------------------------------------*/ for (mot=1; motunique = 1; break; case OPTION_SANS_SYMETRIE : options->symetries = 0; break; case OPTION_NOMBRE_SOLUTIONS : options->nombre = 1; break; case OPTION_MAN : Man( ); exit( 0 ); case OPTION_FICHIER_SORTIE : if( options->nom_f_sortie ) return( 1 ); else option_o_lue = 1; break; default : return( 1 ); } lettre ++; } } else { if( option_o_lue ) if ( ! options->nom_f_sortie ) options->nom_f_sortie = argv[mot]; else return( 1 ); else if ( ! options->nom_f_entree ) options->nom_f_entree = argv[mot]; else return( 1 ); } } if( ! options->nom_f_entree ) return( 1 ); return( 0 ); } /*============================================================================*/ /* Programme principal */ /*============================================================================*/ int main( int argc, char *argv[] ) { Surface surface; /* Surface a paver. */ Pieces *pieces; /* Pointeurs sur les pieces. */ FILE* sortie; /* Fichier de sortie. */ Options options; /* Options de la ligne de commandes. */ int retournee; /* Doit-on retourner la figure ? */ /*----------------------------------------------------------------------------*/ /* Lecture des arguments */ /*----------------------------------------------------------------------------*/ if( Arguments( argc, argv, &options ) ) { Usage( argv ); exit( 1 ); } /*----------------------------------------------------------------------------*/ /* Lecture de la surface a paver. */ /*----------------------------------------------------------------------------*/ if( Lecture( options.nom_f_entree, &surface, &retournee ) != 0 ) exit(1); /*----------------------------------------------------------------------------*/ /* Choix de la fonction d'affichage. */ /*----------------------------------------------------------------------------*/ if( options.unique ) if( retournee ) surface.Affichage = Affiche_Une_Solution_Retournee; else surface.Affichage = Affiche_Une_Solution; else if( options.symetries ) if( retournee ) surface.Affichage = Affiche_Solution_Retournee; else surface.Affichage = Affiche_Solution; else if( retournee ) surface.Affichage = Affiche_Solution_Sans_Symetries_Retournee; else surface.Affichage = Affiche_Solution_Sans_Symetries; /*----------------------------------------------------------------------------*/ /* Initialisations. */ /*----------------------------------------------------------------------------*/ Ouvrir_Fichier_Solutions ( &sortie, options.nom_f_sortie ); Recherche_Symetries( &surface ); pieces = Creation_Pieces( ); /*----------------------------------------------------------------------------*/ /* Recherche des solutions. */ /*----------------------------------------------------------------------------*/ Pavage( sortie, &surface, *pieces ); if( options.nombre ) fprintf( sortie, "Nombre de solutions : %d\n", surface.nb_sol ); /*----------------------------------------------------------------------------*/ /* Avant de partir ... */ /*----------------------------------------------------------------------------*/ Fermer_Fichier_Solutions( sortie ); free( surface.clos ); free( surface.buf ); free( surface.Grille ); return( 0 ); } /******************************************************************************/ /* Fin du fichier pento.c */ /******************************************************************************/