Tuesday, June 26, 2007

A Cryptarithmetic Solver


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:

Anonymous said...

i want a Program for solving the CRYPTARITHMETIC problem

Anonymous said...

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 said...
This comment has been removed by a blog administrator.
Anonymous said...
This comment has been removed by a blog administrator.
Abhiram said...

@Anonymous 1: Check the post itself. I have uploaded the code.

@Anonymous 2: Thanks :)

Anonymous said...

wat constraint satisfaction problem algorithm did you use in solving this?

Abhiram said...

^^^: I don't use any CSP algorithm; I have used brute force.