I- Présentation du problème

A) Les entrées

On nous fournit:

• Un entier N (2 ≤ N ≤ 5), qui représente le nombre de mots à additionner;
• N chaînes de caractères mots, chacune représentant un mot à additionner;
• Une dernière chaîne de caractères totalStr représentant le total de l’addition des mots précédents.

B) But du jeu

Pour résoudre ce problème, il faut écrire un programme en C qui résout un cryptarithme, c'est-à-dire une équation dans laquelle les chiffres ont été remplacés par des lettres. Dans ce problème, chaque cryptarithme est une addition entre plusieurs mots. Le programme devra trouver et afficher l’unique correspondance entre chaque lettre et un chiffre (de 0 à 9). Il faut donc analyser et attribuer un chiffre à chaque lettre, en respectant les règles suivantes :

• Une même lettre représente toujours le même chiffre;
• Deux lettres distinctes ne peuvent pas correspondre au même chiffre;
• Aucune lettre placée en tête d’un mot ne peut être associée au chiffre 0.

Ce programme devra donc trouver la correspondance correcte entre les lettres et les chiffres afin de satisfaire l’équation du cryptarithme.

C) La sortie

On doit retourner toutes les lettres ainsi que leur valeur respective. L'affichage se fait ligne après ligne avec une lettre et son chiffre correspondant par ligne.

II- Ma méthode de résolution

A) Approche synoptique

J'analyse d'abord les données en identifiant les éléments clés du problème : les mots à additionner, ainsi que le mot total. Ensuite, j'extrais toutes les lettres distinctes présentes dans ces mots et les as organisées pour faciliter leur traitement. Ensuite, pour attribuer un chiffre à chaque lettre, j'explore différentes combinaisons possibles en générant des affectations de chiffres aux lettres tout en respectant les contraintes du problème. Cette exploration s’est faite de manière systématique afin de tester chaque possibilité. À chaque étape, je vérifie si l’association des lettres aux chiffres donnait une addition correcte. Dès qu’une configuration valide a été trouvée, j'affiche le résultat en respectant l’ordre alphabétique des lettres.

B) Approche algorithmique et explication de mon programme

Tout d'abord, mon programme commence par récupérer le nombre de mots à additionner ainsi que les mots eux-mêmes, suivis du mot représentant le total attendu. Il parcourt tous les mots et identifie quelles lettres sont présentes dans l’équation, ensuite, il trie ces lettres par ordre alphabétique afin de garantir un affichage structuré. Il faut ensuite que le programme génére les différentes permutations, pour cela le programme cherche toutes les façons possibles d’attribuer un chiffre (de 0 à 9) à chaque lettre unique. Il utilise une approche récursive qui explore toutes les combinaisons valides tout en respectant les contraintes du problème (par exemple, une lettre en début de mot ne peut pas être associée à 0). Une fois une possibilité déterminé, il faut vérifier si cette solution fonctionne, donc, pour chaque permutation générée, il convertit les mots en nombres en remplaçant les lettres par leurs chiffres associés. Une fois les mots convertient, le programme effectue l’addition des N mots et vérifie si la somme obtenue correspond bien au total donné dans l’entrée. Pour finir, lorsqu’une permutation valide est trouvée, il affiche chaque lettre suivie du chiffre qui lui est associé, en respectant l’ordre alphabétique.

 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define MAX_LETTRES 10
 
#define MAX_MOTS 5
 
#define MAX_LONGUEUR 100
 
int verifier_solution(char mots[MAX_MOTS][MAX_LONGUEUR], int N, char totalStr[MAX_LONGUEUR], int chiffres[], char lettres[], int nb_lettres) {
    int valeurs[N + 1];
 
    for (int i = 0; i < N + 1; i++) {
        valeurs[i] = 0;
        char *mot = (i < N) ? mots[i] : totalStr;
        for (int j = 0; j < strlen(mot); j++) {
            int index = strchr(lettres, mot[j]) - lettres;
            valeurs[i] = valeurs[i] * 10 + chiffres[index];
        }
    }
 
    int somme = 0;
    for (int i = 0; i < N; i++) {
        somme += valeurs[i];
    }
 
    return (somme == valeurs[N]);
}
 
void permuter(int chiffres[], int index, int utilisé[], char mots[MAX_MOTS][MAX_LONGUEUR], int N, char totalStr[MAX_LONGUEUR], char lettres[], int nb_lettres) {
    if (index == nb_lettres) {
        if (verifier_solution(mots, N, totalStr, chiffres, lettres, nb_lettres)) {
            for (int i = 0; i < nb_lettres; i++) {
                printf("%c %d\n", lettres[i], chiffres[i]);
            }
        }
        return;
    }
 
    for (int i = 0; i < 10; i++) {
        if (!utilisé[i]) {
            int est_premiere_lettre = 0;
            for (int j = 0; j < N + 1; j++) {
                char *mot = (j < N) ? mots[j] : totalStr;
                if (lettres[index] == mot[0]) {
                    est_premiere_lettre = 1;
                    break;
                }
            }
 
            if (est_premiere_lettre && i == 0)
                continue;
 
            chiffres[index] = i;
            utilisé[i] = 1;
            permuter(chiffres, index + 1, utilisé, mots, N, totalStr, lettres, nb_lettres);
            utilisé[i] = 0;
        }
    }
}
 
int main() {
    int N;
    scanf("%d", &N);
 
    char mots[MAX_MOTS][MAX_LONGUEUR];
    for (int i = 0; i < N; i++) {
        scanf("%s", mots[i]);
    }
 
    char totalStr[MAX_LONGUEUR];
    scanf("%s", totalStr);
 
    char lettres[MAX_LETTRES] = "";
    for (int i = 0; i < N + 1; i++) {
        char *mot = (i < N) ? mots[i] : totalStr;
        for (int j = 0; j < strlen(mot); j++) {
            if (!strchr(lettres, mot[j])) {
                int len = strlen(lettres);
                lettres[len] = mot[j];
                lettres[len + 1] = '\0';
            }
        }
    }
 
    // Trier les lettres par ordre alphabétique
    int nb_lettres = strlen(lettres);
    qsort(lettres, nb_lettres, sizeof(char), (int (*)(const void *, const void *)) strcmp);
 
    int chiffres[MAX_LETTRES], utilisé[10] = {0};
 
    permuter(chiffres, 0, utilisé, mots, N, totalStr, lettres, nb_lettres);
 
    return 0;
}

III- Un autre programme

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
 
int N, letters, digit_used[10], letter_to_digit[10];
char word[6][11], letter[11], *p, line[6][11];
 
int cmp(const void *a, const void *b){ return *(char*)a - *(char*)b; }
 
int is_initial(char c){
    for(int i = 0; i <= N; i++)
        if(word[i][0] == c) return 1;
    return 0;
}
 
void test(){
    for(int i = 0; i <= N; i++)
        for(int j = 0; word[i][j]; j++)
            for(int k = 0;; k++)
                if(word[i][j] == letter[k]){
                    line[i][j] = letter_to_digit[k] + '0';
                    break;
                }
    int sum = 0;
    for(int i = 0; i <= N; i++)
        sum += atoi(line[i]) * (i == N ? -1 : 1);
    if(sum) return;
    for(int i = 0; i < letters; i++)
        printf("%c %i\n", letter[i], letter_to_digit[i]);
    exit(0);
}
 
void assign(int i){
    letter_to_digit[i] = is_initial(letter[i]);
    for(; letter_to_digit[i] <= 9; letter_to_digit[i]++)
        if(digit_used[letter_to_digit[i]] == 0){
            if(i == letters - 1) test();
            else
                digit_used[letter_to_digit[i]] = 1,
                assign(i + 1),
                digit_used[letter_to_digit[i]] = 0;
        }
}
 
int main(){
    scanf("%d", &N);
    for(int i = 0; i <= N; i++)
        for(scanf("%s", p = word[i]); *p; p++)
            if(strchr(letter, *p) == 0) letter[letters++] = *p;
    qsort(letter, letters, sizeof(char), cmp);
    assign(0);    
}

Ce programme extrait directement les lettres uniques lors de la lecture des mots, alors que ton programme les rassemble après coup. Il trie ces lettres avec qsort, tout comme toi. Pour attribuer des chiffres, il utilise une affectation récursive qui évite 0 pour les lettres initiales dès le départ, tandis que toi, tu vérifies cela pendant les permutations. Il reconstruit les valeurs numériques des mots avec atoi, ce qui est plus direct que ton approche basée sur la multiplication progressive. Enfin, il s’arrête immédiatement (exit(0)) dès qu’une solution valide est trouvée, alors que ton programme teste toutes les permutations avant d'afficher la solution. Cela le rend potentiellement plus rapide dans certaines configurations.

Vous trouverez ici la page de téléchargement des fichiers concernant le rapport cryptarithm.