// Lösen von Textsummen-Denksportaufgaben mittels Backtracking
//
// Aufruf: textsumme operand1 operand2 summe
//
// Klaus Kusche

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <stdbool.h>

// Maximale Länge der Wörter
#define MAX_WORTLEN 32

// die in der Aufgabe vorkommenden Buchstaben (max. 10, siehe buch_anz)
char buchst[10];

// deren Anzahl
int buch_anz = 0;

// die zum i-ten Buchstaben in buchst gehörige Ziffer
// für noch nicht belegte Buchstaben ist ziffer[i] gleich -1
// ziffer[10] ist 0 (für die führenden Leerzeichen in den Worten),
// das spart ein paar if
int ziffer[11];

// kleinster Wert für den i-ten Buchstaben
// 1 für Buchstaben, die am Anfang eines Wortes stehen (dürfen nicht 0 werden),
// 0 für alle anderen
int anfang[10];

// ist die Ziffer i schon verwendet?
// (damit wir nicht jedesmal "ziffer" komplett durchsuchen müssen)
bool belegt[10];

// die Eingabe-Wörter in interner Darstellung:
// * Buchstaben werden ersetzt durch ihren Index in "buchst" und "ziffer"
//   ==> ziffer[op1[i]] liefert die Ziffer,
//       die für den i-ten Buchstaben des ersten Wortes eingesetzt wurde,
//       oder -1, wenn dem i-ten Buchstaben noch keine Ziffer zugeordnet wurde,
//       oder 0, wenn der i-te Buchstabe ein führendes Leerzeichen ist.
// * alle Wörter gleichlang (wort_len Elemente)
// * rechtsbündig, vorne aufgefüllt mit 10 (für den Zugriff auf ziffer[10])
short int op1[MAX_WORTLEN];
short int op2[MAX_WORTLEN];
short int sum[MAX_WORTLEN];

// Anzahl der Werte in op1, op2 und sum = Länge des längsten Eingabe-Wortes
int wort_len;

// für Fehlermeldungen
const char *prog_name;

// Aufrufzähler
int callcnt = 0;

int buchstabe(char c);
void eingabe(int argc, const char *argv[]);
bool sinnvoll(void);
bool loesung(int pos);
void print_wort(const short int wort[]);
void ausgabe(void);

int main(int argc, const char *argv[])
{
  prog_name = argv[0];
  
  eingabe(argc, argv);
  
  if (!loesung(0)) {
    printf("Keine Lösung!\n");
  }

  printf("%d Aufrufe\n", callcnt);
  
  exit(EXIT_SUCCESS);
}

// liefert den Index von c in "buchst"
// prüft, ob c gültig ist
// hängt ihn an "buchst" an, wenn er neu ist
int buchstabe(char c)
{
  int i;

  if (!isalpha(c)) {
    fprintf(stderr, "%s: Bitte nur Buchstaben eingeben! (%c?)\n", prog_name, c);
    exit(EXIT_FAILURE);
  }

  for (i = 0; i < buch_anz; ++i) {
    if (buchst[i] == tolower(c)) {
      return i;
    }
  }

  if (buch_anz == 10) {
    fprintf(stderr,
      "%s: Die Eingabe darf maximal 10 verschiedene Buchstaben enthalten\n",
      prog_name);
    exit(EXIT_FAILURE);
  }

  buchst[buch_anz] = tolower(c);
  return buch_anz++;
}

void eingabe(int argc, const char *argv[])
{
  int l1, l2, l3, i;
  
  if (argc != 4) {
    fprintf(stderr, "Aufruf: %s operand1 operand2 summe\n", prog_name);
    exit(EXIT_FAILURE);
  }

  for (i = 0; i < 10; ++i) {
    belegt[i] = false;
    ziffer[i] = -1;
    anfang[i] = 0;
  }
  ziffer[10] = 0;

  l1 = strlen(argv[1]);
  l2 = strlen(argv[2]);
  l3 = strlen(argv[3]);

  wort_len = l1;
  if (l2 > wort_len) wort_len = l2;
  if (l3 > wort_len) wort_len = l3;
  if (wort_len > MAX_WORTLEN) {
    fprintf(stderr, "%s: Maximale Wortlänge %d\n", prog_name, MAX_WORTLEN);
    exit(EXIT_FAILURE);
  }
  if ((l1 == 0) || (l2 == 0) || (l3 == 0)) {
    fprintf(stderr, "%s: Bitte keine leeren Worte\n", prog_name);
    exit(EXIT_FAILURE);
  }

  // man kommt am schnellsten zu Ergebnissen,
  // wenn man die Zeichen der Eingabeworte
  // in buchst spaltenweise von hinten nach vorne speichert!
  // ==> Backtracking löst hinterste Spalte zuerst, dann zweit-hinterste, ...
  for ( i = wort_len - 1; i >= 0; --i) {
    op1[i] = (i < wort_len - l1) ? 10 : buchstabe(argv[1][i - (wort_len - l1)]); 
    op2[i] = (i < wort_len - l2) ? 10 : buchstabe(argv[2][i - (wort_len - l2)]); 
    sum[i] = (i < wort_len - l3) ? 10 : buchstabe(argv[3][i - (wort_len - l3)]); 
  }

  // die vordersten Buchstaben jedes Wortes dürfen nicht mit 0 belegt werden
  anfang[buchstabe(argv[1][0])] = 1;
  anfang[buchstabe(argv[2][0])] = 1;
  anfang[buchstabe(argv[3][0])] = 1;
}

#if 0
// können die bisher in "ziffer" gespeicherten Ziffern noch eine Lösung ergeben?
// "false" wenn jetzt schon ein Rechenfehler in der Lösung ist, "true" sonst
// einfachere Variante: Prüft nur bis zur ersten Spalte,
// die noch unbekannte Werte enthält
bool sinnvoll(void)
{
  int o1, o2, s;  // Ziffern in der aktuellen Spalte
  int summe;      // Spaltensumme
  int ue = 0;     // 0 ... kein Übertrag, 1 ... Übertrag
  int i;
  
  // geh die Worte von hinten nach vorne durch (letzte Spalte zuerst)
  // (erstens weil der Übertrag von hinten nach vorne gerechnet werden muss,
  // und zweitens weil das Backtracking die Buchstaben von hinten her füllt)
  for (i = wort_len - 1; i >= 0; --i) {
    o1 = ziffer[op1[i]];
    o2 = ziffer[op2[i]];
    s = ziffer[sum[i]];
    // unbekannte Ziffern in o1, o2 oder s haben Wert -1
    if ((o1 < 0) || (o2 < 0) || (s < 0)) {
      // noch Werte der Spalte unbekannt
      // ==> hör auf zu prüfen und nimm an, es könnte noch klappen
      return true;
    }
    summe = o1 + o2 + ue;
    if (summe < 10) {
      // kein neuer Übertrag
      if (summe != s) return false;
      ue = 0;
    } else {
      // Spalte erzeugt Übertrag
      if (summe - 10 != s) return false;
      ue = 1;
    }
  }
  // alle Spalten sind belegt und wurden geprüft, keine falsche Spalte gefunden
  if (ue == 1) {
    // die Summe aller Spalten würde stimmen,
    // aber in der vordersten Spalte bleibt ein Übertrag ==> passt nicht
    return false;
  }
  return true;
}
#else
// können die bisher in "ziffer" gespeicherten Ziffern noch eine Lösung ergeben?
// "false" wenn jetzt schon ein Rechenfehler in der Lösung ist, "true" sonst
// komplizierte Variante, prüft immer alle Spalten,
// auch wenn sie noch nicht komplett ausgefüllt sind.
bool sinnvoll(void)
{
  int o1, o2, s;  // Ziffern in der aktuellen Spalte
  int summe;      // Spaltensumme
  int ue = 0;     // 0 ... kein Übertrag, 1 ... Übertrag, -1 ... Ü unbekannt
  int i;
  
  // geh die Worte von hinten nach vorne durch (letzte Spalte zuerst)
  // (erstens weil der Übertrag von hinten nach vorne gerechnet werden muss,
  // und zweitens weil das Backtracking die Buchstaben von hinten her füllt)
  for (i = wort_len - 1; i >= 0; --i) {
    o1 = ziffer[op1[i]];
    o2 = ziffer[op2[i]];
    s = ziffer[sum[i]];
    // unbekannte Ziffern in o1, o2 oder s haben Wert -1
    if ((o1 >= 0) && (o2 >= 0)) {
      // die Ziffern der Summanden in der Spalte sind schon bekannt
      if (ue >= 0) {
        // der Übertrag aus der vorigen Spalte ist auch bekannt
        // ==> Summe muss genau passen
        summe = o1 + o2 + ue;
        if (summe < 10) {
          // kein neuer Übertrag
          // prüfe Summe falls bekannt
          if ((s >= 0) && (summe != s)) return false;
          ue = 0;
        } else {
          // Spalte erzeugt Übertrag
          // prüfe Summe falls bekannt
          if ((s >= 0) && (summe - 10 != s)) return false;
          ue = 1;
        }
      } else {
        // der Übertrag aus der vorigen Spalte ist unbekannt
        // ==> summe könnte auch 1 höher sein
        summe = o1 + o2;
        if (summe < 9) {
          // sicher kein neuer Übertrag
          if ((s >= 0) && (summe != s) && (summe + 1 != s)) return false;
          ue = 0;
        } else if (summe >= 10) {
          // Spalte erzeugt sicher Übertrag
          if ((s >= 0) && (summe - 10 != s) && (summe - 10 + 1 != s)) return false;
          ue = 1;
        } else {
          // summe == 9, mit altem Übertrag 10
          // ==> Spalte kann Übertrag erzeugen oder nicht...
          if (s >= 0) {
            if ((s != 9) && (s != 0)) return false;
            ue = (s == 9) ? 0 : 1;
          } else {
            ue = -1;
          }
        }
      }
    } else {
      // die Spalte enthält noch unbekannte Ziffern
      // ==> der aus dieser Spalte resultierende Übertrag ist unbekannt
      ue = -1;
    }
  }
  // alle Spalten wurden geprüft, keine offensichtlich falsche Spalte gefunden
  if (ue == 1) {
    // die Summe aller Spalten würde stimmen,
    // aber in der vordersten Spalte bleibt ein Übertrag ==> passt nicht
    return false;
  }
  return true;
}
#endif

// löse ab dem Buchstaben mit Index "pos" in den Arrays buchst und ziffer
// wenn pos schon buch_anz ist (alle Buchstaben belegt): ausgabe() aufrufen!
// jede Ebene der Rekursion löst *einen* Buchstaben, nämlich buchst[pos]
// d.h. belegt das Element ziffer[pos] mit der zu buchst[pos] gehörenden Ziffer
//      und markiert die gewählte Ziffer im Array belegt als belegt
// Returnwert: true ... Lösung gefunden, false ... Keine Lösung
//             (brauchen wir für die Ausgabe "Keine Lösung!" im main)
bool loesung(int pos)
{
  // der Returnwert:
  // falsch wenn die Schleife unten für keine einzige Möglichkeit eine Lösung findet
  bool lsg = false;
  int i;

  ++callcnt;

  if (pos == buch_anz) {
    // alle Buchstaben gültig belegt ==> richtige Lösung gefunden, ausgeben!
    ausgabe();
    return true;
  }

  // probier alle Ziffern ab 0 oder 1 für den Buchstaben Nummer pos
  for (i = anfang[pos]; i < 10; ++i) {
    if (!belegt[i]) {     // die Ziffer ist noch unbenutzt
      ziffer[pos] = i;    // speichere die Ziffer in der Lösung
      belegt[i] = true;   // markiere die Ziffer als "verwendet"
      if (sinnvoll()) {
        // dieser Buchstabe passt, suche Lösung für den nächsten Buchstaben
        if (loesung(pos + 1)) {
          lsg = true;
        }
        // else: diese Möglichkeit für den Buchstaben pos
        // kann nicht zur Lösung führen ==> nicht weiter verfolgen
      }
      // egal ob Lösung oder nicht:
      // Die Belegung des Buchstaben pos wieder rückgängig machen
      belegt[i] = false;  // markiere die Ziffer wieder als "frei"      
      ziffer[pos] = -1;   // lösche die Ziffer wieder aus der Lösung
    }
    // else nichts: Ignoriere diese Ziffer, probier die nächste
  }
  return lsg;
}

// gib die dem Wort (op1, op2, sum) entsprechende Ziffernfolge aus
void print_wort(const short int wort[])
{
  int i;

  for (i = 0; i < wort_len; ++i) {
    if (wort[i] == 10) putchar(' ');
    else putchar('0' + ziffer[wort[i]]);
  }
  putchar('\n');
}

void ausgabe(void)
{
  int i;

  for (i = 0; i < buch_anz; ++i) {
    printf("%c=%d%s", buchst[i], ziffer[i], (i == buch_anz - 1) ? "\n" : ", ");
  }
  print_wort(op1);
  print_wort(op2);
  print_wort(sum);
  putchar('\n');
}