Today in class my professor was describing this problem. We thought about it for a while, and than he started describing the brute force solution. His code was six nested for loops. I assumed there had to be a better way to represent this problem, so I wrote a script to solve this and other similar problems.
I am happy with the solution I arrived at, other than two small points. I wish I could get out of the habit of thinking of lists in terms of their indexes. You can see on line 37 where I am generating each mapping of numbers to letters, my dictionary comprehension relies on ‘range(len(trial))’. This solution also runs in n! time, but that is just because of how hard of a problem it is.
This problem is NP-Complete. This explains why it has such a high complexity. It is important to note that this problem is bounded where n<10, as you can only have that many unique letters representing unique numbers.