
If you are reading this post, I assume you know what cryptarithmetic puzzles are, so I shall not belabor the point. In case you do not, please check
this for a complete explanation. I also found some interesting papers on the topic. Check
them out if you want to.
I have written a program in C which solves any cryptarithmetic equation (have tested it extensively on a lot of examples online). The input consists of three strings say S1, S2 and S3 and then a number (1 or 2 or 3 or 4), which denotes the operators + or - or * or / respectively. The programs generates all possible solutions for the crptarithmetic equation S1 (operator) S2 = S3.
LOGIC:-
There is nothing extra-ordinary in the logic. It is just a simple combinatorial technique, wherein I check all possibilities and output only the correct ones.
1. Take the unique characters.
2. Assign one possible set of values that you have not tried before. If no further assignments possible, exit.
3. Check it the assignment is correct.
4. If correct, the print the solution. Go to step 2.
crypt(letters,index)
{
......if all letters are assigned and the assignment is correct
...............print the solution;
...............return;
......for i = [0,10)
..........if i has not yet been assigned
................assign i to letters[index]
................crypt(letters,index+1); //recursive call
}
main()
{
........get the unique letters among the three strings
........call crypt(letters,0);
}
You can find plenty of places online which give you such puzzles. You can download the code from
here. I have on purpose separated the entire program into many modules, more than what I would normally think was necessary. Minor optimizations are still possible, but I have refrained from doing them so as to not make the program look far too obfuscated. Please do report any errors that you find. Thank you.
7 comments:
i want a Program for solving the CRYPTARITHMETIC problem
I found this site using [url=http://google.com]google.com[/url] And i want to thank you for your work. You have done really very good site. Great work, great site! Thank you!
Sorry for offtopic
@Anonymous 1: Check the post itself. I have uploaded the code.
@Anonymous 2: Thanks :)
wat constraint satisfaction problem algorithm did you use in solving this?
^^^: I don't use any CSP algorithm; I have used brute force.
Post a Comment