an interesting problem ( help me please ! )

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

an interesting problem ( help me please ! )

Post by hank » Sat Oct 04, 2003 4:25 pm

Hi,

Cryptarithmetic Puzzle
A cryptarithm is an arithmetic formula in which the digits are replaced by other symbols. Cryptarithms can be additions, multiplications, or divisions. For example,

SEND + MORE = MONEY
9567 + 1085 = 10652

WHO * IS = MOSIS
421 * 75 = 31575

LINK / NET = KT ... KEY
6041 / 453 = 13 ... 152

Conventionally following rules must be followed for the cryptarithms:

1. There must be a one-to-one mapping between symbols and digits.
2. When symbols are replaced by their digits, the formula must be correct.
3. The numerical base is 10.
4. Numbers must not begin with a zero.
5. There must be only one solution to the cryptarithm.

In this problem, you are going to solve cryptarithmetic additions that may have multiple addends. However, you should determine whether the cryptarithm has only one solution.

Input
There are multiple cryptarithms in the input file. Each line has one equation. On the right side of the equal sign, there is only one word. On the left side of the equal sign, there are two or more words, which are separated by plus signs. Each word consists of one or more uppercase letters. You may assume there are no more than 80 characters in a line.

Output
For each input, your program should print exactly one line of output. If the cryptarithm has exactly one solution, print the solution in which the letters of the cryptarithm are replaced by their digits. If the cryptarithm cannot be solved or it has more than one solution, print

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Sun Oct 05, 2003 10:26 am

if you use a constraint-based language the problem is very easy, see for example the following PROLOG program

Code: Select all

smm(S,E,N,D,M,O,R,Y) :-
	domain([S,E,N,D,M,O,R,Y], 0, 9),
	sconstrain(S,E,N,D,M,O,R,Y),
	labeling([], [S,E,N,D,M,O,R,Y]).
	
sconstrain(S,E,N,D,M,O,R,Y) :-
	S #\= 0, M #\= 0,
	all_different([S,E,N,D,M,O,R,Y]),
		1000*S + 100*E + 10*N + D
	+	1000*M + 100*O + 10*R + E
	#= 10000*M + 1000*O + 100*N + 10*E + Y.
(If you don't know the PROLOG syntax I'm sure you can figure it out :P)

But I have to admit that this is basically a "try all" solution, however it cuts your search space significantly by applying the constraints. My feeling is that there is no solution with an efficient (polynomial) worst case running time, but I might be wrong here.

[/code]

Post Reply

Return to “Algorithms”