C++에서 암호 해독 솔버 만들기

Question

암호 해독 퍼즐을 나타내는 3 개의 문자열을 사용하는 C++ 프로그램을 계획 중입니다. 입력이 오른쪽으로 정렬 것으로 가정하여 예를 들어, 두, 두, 4 주어, 프로그램,

TWO 
+ TWO 
------ 
    FOUR 

에 해당하는 같은 수식하는 각 문자에 자리 대체를 찾을 것입니다. 이것에 관해가는 한 가지 방법은 당연히 무작위로 강제하는 것입니다. 각 문자에 대해 가능한 모든 대체 문자를 중첩 된 루프로 할당하고, 반복하여 합계를 시도하는 등의 작업을 수행 할 것입니다.

내 생각에 이것은 극도로 비효율적이지만 기본 루프 검사는 각 변수의 도메인을 제한하기 위해 일련의 공제가 수행 된 후 실행 가능한 (또는 필요한) 방법 일 수 있습니다. 저는 시각화하기가 다소 어려웠습니다. 그러나 이와 같은 일반/패딩 구조를 가정하는 것이 합리적 일 것입니다. 각 X는 꼭 필요하지 않은 별개의 숫자를 나타내며 각 C는 캐리 숫자입니다.이 경우, 0 또는 1 중 하나임)? : 염두에두고

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

는 좀 더 계획의 생각 : 앞에 0 -Though

문제에 주어진되지 않습니다, 나는 아마 곳에 적절한 출력/경기에도 가지 그들을 충분히 추가한다고 피연산자까지

- 각 문자에 대해 0-9의 가능한 값 집합으로 시작해야한다고 생각합니다. 아마도 '도메인'테이블에 벡터로 저장되고 공제액으로 값을 제거해야합니다. 내가 볼 경우 예를 들어, 일부 문자는이

A 
C 
-- 
A 

처럼 줄 지어, 그 C가 제로 말할 수 이것은 그 도메인에서 다른 값을 제거 할 수 있습니다. 꽤 많은 공제액을 생각할 수 있지만, 모든 종류의 작은 상황에 대해 일반화하고 코드에 넣는 것은 언뜻보기에는 까다로울 수 있습니다.

-Assuming 도메인 테이블에서 많은 것들을 실행하고 많은 값을 부팅하는 추리가 있습니다. 모든 것을 반복하고 상태 공간이 작아서 솔루션을 합리적인 시간 내에 그러나 그것은 그것보다 더해야 할 것처럼 느껴집니다! - 어쩌면 몇 가지 똑똑한 방정식이나 그 선을 따라 뭔가를 설정할 수 있습니다.

팁 감사합니다.

Answer 1

암호 해독 문제는 고전 constraint satisfaction problems입니다.

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

일반화 된 의사 :

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] 

기본적으로, 당신이해야 할 것은, 당신의 주어진 예제를 사용하여 프로그램을 사용하면 다음과 같은 결과가 발생하도록 입력에 따라 제약을 생성 가지고있다 당신 그래서 예를 들면

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

:

문제의 정의에 따라 추가 제약

Range(O, W, T) == {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 
Range(Carry1, Carry2, F) == {0, 1} 

검색 공간을 제한하기 위해 제약 조건을 생성했으면 링크 된 기사에서 설명한 CSP 해결 방법을 사용하여 검색 공간을 이동하고 솔루션 (해당되는 경우)을 결정할 수 있습니다. (로컬) 일관성의 개념은 여기에서 매우 중요하며이를 활용하면 CSP의 검색 공간을 크게 줄일 수 있습니다.

단순한 예로 암호 연산은 일반적으로 앞의 0을 사용하지 않으므로 결과가 두 입력보다 길면 마지막 자리 (예 : 마지막 자리수)가 1이어야합니다 (예 : F == 1). 이 제약 조건은 역으로 전파 될 수 있습니다. 즉, 2T + Carry2 == O + 10; 즉 Carry2은 1과 2 (4) +1 == 9 일 수 있으므로 T의 최소값은 5 ​​여야합니다. 검색을 향상시키는 다른 방법 (최소 충돌 알고리즘 등)이 있지만이 대답을 본격적인 CSP 클래스로 바꾸지는 않으므로 추가 조사를 맡을 것입니다.

(당신이 A+C=A 같은 가정을 만들 수 없습니다 - 그 의미 하는가 인해 C 9 인의 가능성과 1 인 컬럼에 캐리 자리에 적어도 상당한 열을 제외>C == 0 일반 의지에 C 그 도메인 {0, 9}으로 제한 될 수 있으므로 완전히 해제되지 않았습니다.)

Answer 2

오른쪽에서 왼쪽으로이 문제를 반복 할 수 있습니다. 즉, 실제 작업을 수행하는 방식입니다. 맨 오른쪽 열에서 시작하십시오. 발생하는 모든 숫자에 대해 해당 숫자에 대한 할당이 이미 있는지 여부를 확인합니다. 있다면, 당신은 그 가치를 사용하고 계속합니다. 존재하지 않으면 가능한 모든 숫자에 대해 반복문을 입력하고 (예 : 반복적 인지도가 필요한 경우 이미 사용 된 것을 생략 함) 각 가능한 할당을 반복적으로 계속합니다. 합계 행에 도달하면 거기에 주어진 숫자에 대한 변수가 이미 할당되어 있는지 다시 확인합니다. 그렇지 않은 경우, 현재 합계의 마지막 자리수를 지정하고 다음 상위 값 열로 계속 이동하여 나옵니다. 과제가 이미 있고 결과의 마지막 자리에 동의하는 경우 동일한 방법으로 진행합니다. 할당이 있고 동의하지 않으면 현재 분기를 중단하고 다른 숫자를 선택할 수있는 가장 가까운 루프로 돌아갑니다.

이 접근법의 이점은 많은 변수가 앞에 추측되는 대신 합계에 의해 결정된다는 것입니다. 특히 합계 행에서만 발생하는 문자의 경우 이는 큰 이점이 될 수 있습니다.또한 오류를 일찍 찾아 낼 수 있으므로 지금까지 선택한 내용이 이미 일관성이없는 경우 문자의 선택을 피할 수 있습니다. 단점은 프로그램의 다소 복잡한 재귀 구조 일 수 있습니다. 그러나 일단 당신이 그렇게하면, 생각을 코드로 바꾸는 것에 관해 많은 것을 배울 것입니다.

Answer 3

난 blog 무작위 힐 클라이밍 알고리즘을 사용하여이 문제를 해결했습니다. 기본 아이디어는 글자에 숫자를 무작위로 할당하고 방정식의 양측 간의 차이를 계산하여 과제에 "점수를 매기고 과제를 바꾸거나 (점수를 재 계산하여) 점수를 재 계산하여 개선 된 변화를 유지하는 것입니다. 그 점수는 점수를 매기고 그렇지 않은 점수는 무시합니다. 그것은 언덕길입니다. 왜냐하면 오직 한 방향으로 만 변화를 수용하기 때문입니다. 언덕 등반의 문제점은 때로는 현지 최대치에 머물러 있기 때문에 현재의 시도를 버리고 처음부터 다시 시작해야합니다. 그것이 알고리즘의 랜덤 화 부분입니다. 알고리즘은 매우 빠릅니다. 즉, 모든 초당 암호를 초 단위로 해결합니다.