About half year ago, there was a hot topic in the internet about the difficulty of a primary one student homework in Hong Kong. As shown below, this is a cryptarithm problem, where each character represents a unique number from 0 to 9.
After that, one of the parents wrote a brute-force solution and post it to the forum. All of sudden, people start to shift the focus and have a seriously discussion on scalability and efficiency of the program. Some people start to come up with their ‘best’ solution in various languages.
Despite the fact that doing these questions without programming can train student’s spatial intelligence, in practical situation, neither solving with your own algorithm or without any program is time-efficient when the problem comes to a large scale.
Thanks to Coursera and the University of Melbourne, I recently came across the Modeling Discrete Optimization course which teaches a constraint modeling language called MiniZinc, which allowed us to communicate with constraint solvers written by hundreds of researchers to solve our problem.
As you can see from above, with just a few lines of code, we can get a solution in 46 ms. Isn’t it amazing?! (comparing to writing a brute force solution :] ) Also, it supports getting all feasible solutions or optimize the objective value, say, minimize the sum of all variable.
I strongly recommend students to take the coursera course and learn MiniZinc . First of all, converting a question into a model is an important skill set which is often used in Mathematics. Secondly, you barely can write a better algorithm to solve the problem efficiently unless intensely trained in the field. Lastly, modeling language is more human readable and interpretable than other programming language.
So, Let’s get started!
See: MiniZinc code for the cryptarithm solution.