Creazione di un risolutore crittografico in C++

Question

Sto pianificando un programma C++ che impiega 3 stringhe che rappresentano un puzzle crittografico. Ad esempio, dato due, due e quattro, il programma avrebbe trovato sostituzioni cifre per ogni lettera in modo tale che l'espressione matematica

TWO 
+ TWO 
------ 
    FOUR 

è vero, con gli ingressi assunti come giustificato a destra. Un modo per ovviare a questo sarebbe naturalmente la forza bruta, assegnando ogni possibile sostituzione per ogni lettera con cicli annidati, provando ripetutamente la somma, ecc., Fino a quando la risposta non viene trovata.

Il mio pensiero è che sebbene questo sia terribilmente inefficiente, la sottostante verifica del ciclo può essere una via percorribile (o addirittura necessaria), dopo che una serie di detrazioni viene eseguita per limitare i domini di ciascuna variabile. Sto trovando un po 'difficile da visualizzare, ma sarebbe ragionevole assumere per prima cosa una struttura generale/imbottita come questa (ogni X rappresenta una cifra non necessariamente distinta, e ogni C è una cifra trasporta, che in questo caso, sarà 0 o 1)? :

CCC.....CCC 
    XXX.....XXXX 
+ XXX.....XXXX 
---------------- 
    CXXX.....XXXX 

Con questo in mente, alcuni più pensieri di pianificazione:

-Anche se gli zeri non sarà dato nel problema, probabilmente dovuto aggiungere abbastanza di loro, se del caso, anche le cose/partita operandi

-Sto pensando che dovrei iniziare con un insieme di valori possibili 0-9 per ogni lettera, magari memorizzati come vettori in una tabella 'domini' ed eliminare i valori da questo come deduzioni sono fatte. Ad esempio, se vedo alcune lettere allineate come questo

A 
C 
-- 
A 

, posso dire che C è pari a zero e questo elimino tutti gli altri valori dal suo dominio. Posso pensare ad alcune deduzioni, ma generalizzarle a tutti i tipi di piccole situazioni e metterle in codice sembra un po 'complicato a prima vista.

-Assunzione Ho una buona serie di deduzioni che attraversano le cose e avviano molti valori dalla tabella dei domini, suppongo che continuerei a ripetere tutto e spero che lo spazio degli stati sia abbastanza piccolo da generare un soluzione in un ragionevole lasso di tempo. Ma sembra che ci debba essere più di questo! - Forse qualche equazione intelligente da impostare o qualcosa del genere.

I suggerimenti sono apprezzati!

Answer 1

I problemi di cryptaritmetic sono classici constraint satisfaction problems. In sostanza, ciò che devi fare è avere il vostro programma di generare vincoli in base agli input in modo tale che si finisce con qualcosa di simile a quanto segue, utilizzando la data Esempio:

O + O = 2O = R + 10Carry1 
W + W + Carry1 = 2W + Carry1 = U + 10Carry2 
T + T + Carry2 = 2T + Carry2 = O + 10Carry3 = O + 10F 

pseudocodice generalizzata:

for i in range of shorter input, or either input if they're the same length: 
    shorterInput[i] + longerInput2[i] + Carry[i] = result[i] + 10*Carry[i+1] // Carry[0] == 0 

for the rest of the longer input, if one is longer: 
    longerInput[i] + Carry[i] = result[i] + 10*Carry[i+1] 

vincoli aggiuntivi in ​​base alla definizione del problema:

Range(digits) == {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 
Range(auxiliary_carries) == {0, 1} 

Così, per il tuo esempio:

01.235.164,106174 millions

Una volta generati i vincoli per limitare lo spazio di ricerca, è possibile utilizzare le tecniche di risoluzione CSP come descritto nell'articolo collegato per percorrere lo spazio di ricerca e determinare la soluzione (se ne esiste una, ovviamente). Il concetto di coerenza (locale) è molto importante qui e approfittarne consente di ridurre notevolmente lo spazio di ricerca per i CSP.

Come semplice esempio, si noti che il cryptarithmetic generalmente non utilizza gli zero iniziali, ovvero se il risultato è più lungo di entrambi gli input, la cifra finale, ovvero l'ultima cifra, deve essere 1 (quindi nel proprio esempio significa F == 1). Questo vincolo può quindi essere propagato all'indietro, poiché significa che 2T + Carry2 == O + 10; in altre parole, il valore minimo per T deve essere 5, poiché Carry2 può essere al massimo 1 e 2 (4) + 1 == 9. Esistono altri metodi per migliorare la ricerca (algoritmo min-conflict, ecc.), Ma preferirei non trasformare questa risposta in una vera e propria classe CSP, quindi lascerò ulteriori indagini a voi.

(Si noti che non è possibile fare ipotesi come A+C=A ->C == 0 fatta eccezione per almeno colonna significativo a causa della possibilità di essere C 9 e la cifra portare nella colonna essendo 1. Ciò significa che C a volontà generale essere limitato al dominio {0, 9}, tuttavia, quindi non era completamente fuori con quello.)

Answer 2

Si può iterare su questo problema da destra a sinistra, cioè il modo in cui si eseguirà l'operazione effettiva. Inizia con la colonna più a destra. Per ogni cifra che incontri, controlli se esiste già un incarico per quella cifra. Se c'è, usi il suo valore e vai avanti. In caso contrario, si inserisce un ciclo su tutte le cifre possibili (eventualmente omettendo quelle già utilizzate se si desidera una mappa biiettiva) e si prosegue in modo ricorsivo con ogni possibile assegnazione. Quando raggiungi la riga somma, controlli di nuovo se la variabile per la cifra indicata è già assegnata. In caso contrario, si assegna l'ultima cifra della somma corrente, quindi si continua alla successiva colonna con valore superiore, portando con sé il riporto. Se esiste già un incarico e si concorda con l'ultima cifra del risultato, si procede nello stesso modo. Se c'è un incarico e non è d'accordo, allora si abbandona il ramo corrente e si torna al ciclo più vicino in cui si desiderava scegliere altre cifre.

Il vantaggio di questo approccio dovrebbe essere che molte variabili sono determinate da una somma, invece di indovinare in anticipo. In particolare per le lettere che si verificano solo nella riga somma, questa potrebbe essere una grande vittoria.Inoltre, potresti essere in grado di individuare gli errori nelle prime fasi, evitando così le scelte per le lettere in alcuni casi in cui le scelte fatte fino ad ora sono già incoerenti. Uno svantaggio potrebbe essere la struttura ricorsiva leggermente più complicata del tuo programma. Ma una volta che hai capito bene, avrai anche imparato molto sul trasformare i pensieri in codice.

Answer 3

Ho risolto questo problema nel mio blog utilizzando un algoritmo di scalata in salita casuale. L'idea di base è quella di scegliere un assegnamento casuale di cifre alle lettere, "segnare" l'assegnazione calcolando la differenza tra i due lati dell'equazione, quindi modificare l'assegnazione (scambia due cifre) e ricalcolare il punteggio, mantenendo quelle modifiche che migliorano il punteggio e scartando quelle modifiche che non lo fanno. È una salita in salita, perché accetti solo i cambiamenti in una direzione. Il problema con l'arrampicata in montagna è che a volte si blocca in un massimo locale, quindi ogni tanto butti fuori il tentativo corrente e ricomincia da capo; questa è la parte di randomizzazione dell'algoritmo. L'algoritmo è molto veloce: risolve ogni cryptarithm che ho dato in frazioni di secondo.