boy
+girl
-----
baby
Dovresti risolvere algoritmicamente questo tipo di problema dividendolo in 4 serie di equazioni: il primo per la colonna, il secondo per la colonna delle decine, il terzo per la colonna delle centinaia, il quarto per la colonna delle migliaia. Ogni set calcola la somma usando l'aritmetica modulo-10 (o la base di tua scelta) e calcola il carry nella colonna successiva.
Per ogni serie di equazioni, potresti avere tra 0 e 3 incognite. Con 0 incognite, verificherebbe solo se l'equazione fosse valida. Con uno sconosciuto, potresti risolvere direttamente lo sconosciuto. Con 2 incognite, è possibile scorrere tutte le possibilità per una delle incognite e calcolare l'altra. Infine, per 3 incognite, esegui il looping delle due incognite e calcola il terzo.
Nell'esempio precedente, la colonna ones ha y+l=y , quindi iniziamo con 2 incognite. Quindi esegui un loop sulle possibilità di y (0 ... 9). Partendo da y=0 , risolvendo l'equazione si ottiene l=0 , che non funziona, poiché 0 è già stato assegnato, quindi si passa immediatamente al valore successivo y=1 , e di nuovo si risolve l=0 . A questo punto, calcoliamo il carry (0) e ricontattiamo nella colonna delle decine. Se non trovi una soluzione, passa al valore successivo di y=2 ... fino al raggiungimento di y=9 .
Quindi la prima colonna viene inserita per la prima volta con y=1, l=0, carry=0 . L'equazione o+r+carry=b ha 3 incognite. Quindi, loop over o={2,3,4,5,6,7,8,9} (8 possibilità) e r={2,3,4,5,6,7,8,9}-{o} (7 possibilità). Per quelle 56 combinazioni, calcola b . Se b è una cifra valida (non utilizzata), calcola il carry e recurse in centinaia.
Le centinaia dovrebbero essere prima inserite con y=1, l=0, o=2, r=3, b=5, carry=0 . L'equazione b+i+carry=a ha 2 incognite. Loop over i={4,6,7,8,9} e risoluzione per a . Se a è una cifra valida (non utilizzata), calcola il carry e recurse in migliaia.
Le migliaia dovrebbero essere prima inserite con y=1, l=0, o=2, r=3, b=5, i=4, a=9, carry=0 . L'equazione g+carry=b ha 1 sconosciuto. Calcolando lo sconosciuto troviamo g=5 , ma quella cifra è già utilizzata, quindi torniamo al livello precedente.
-
y ha 10 valori possibili
-
l è calcolato, quindi
-
o quindi ha solo 8 valori possibili e
-
r quindi ha solo 7 valori possibili,
-
b è calcolato, quindi
-
i quindi ha solo 5 possibili valori,
-
a è calcolato,
-
g è calcolato
Questo dà un massimo di
10 x 8 x 7 x 5 = 2800 iterazioni di loop. In realtà, si verificheranno meno iterazioni poiché i valori calcolati generano cifre già utilizzate. Ad esempio, y=0 è stato esplorato solo per il calcolo di l=0 e passando immediatamente al successivo valore possibile per y .
È possibile imporre ulteriori vincoli alle variabili, se necessario. Ad esempio b != 0 e g != 0 , poiché i numeri generalmente iniziano con una cifra diversa da zero.