Each digit to the right determines another one to the left.

Whenever a digit gets repeated you bound.

Taking your decimal case:

> abcd = efgh * i

• Starting with i=1 and h=1 is obviously impossible.
• i * efgh = abcd
• 2 * efg3 = abc6
• 2 * ef13 = ab26 2 repeated bound °
• 2 * ef43 = ab86
• 2 * e543 = (1)086 0 forbidden bound! ²
• 2 * e743 = (1)486 4 repeated bound!
• 2 * e943 = (1)886 8 repeated bound!
• 2 * ef53 = a(1)06 0 forbidden bound! ²
• 2 * ef73 = a(1)46
• 2 * e173 = a346 3 repeated bound
• 2 * e573 = (1)146
• 2 * 8573 = (1)6146 too many digits bound ³
• 2 * 9573 = (1)8146 too many digits bound ³
• 2 * ef83 = a(1)66 6 repeated bound!
• 2 * ef93 = a(1)86
• and so on

°) obviously you can only use 1 when the last multiplication had a carry digit (denoted in brackets) ²) multiplying an even number with 5 will always lead to 0 and multiplying an even number with 6 will always repeat that number ³) the last multiplication in a system with even numbered digits can't have a carry digit

I did this by hand to find some rules to effectively cut down the possibilities of a branch and bound.

Rule 2 means you'll can eliminate all n * (n-1) possibilities where the product repeats one of the factors or lead to 0. For instance in a decimal system i can't possibly ever be 5 or 6.

(just prepare a multiplication table for an n-system to eliminate these cases)

Footnote °) is just a special case of rule 2

Rule 3 means anything i must be < n/2 for n even like the decimal with n=10) and i >= n/2 for n odd.

That is in the decimal case i can only be 2, 3 or 4

These are massive reductions of all possibilities, far more efficient than calculating all k-permutations.

I'm only wondering if it's more efficient to start trying from right to left starting with h or even from left to right starting with e or even combining both possibilities.

for instance these are the only possible combinations of i and e for n=10

  DB<4> for $i (2,3,4) { for $e (1..9) { next if $e == $i or $e*$i >9 
+; print "$i * $e = ", $i *$e,"\n" }}
2 * 1 = 2   #
2 * 3 = 6
2 * 4 = 8  
3 * 1 = 3   #
3 * 2 = 6
4 * 1 = 4   #
4 * 2 = 8
[download]

And the cases I marked with a # mean that the value for f must lead to a carry digit to alter a.

This seems to reduce possible branches very quickly!!!

I hope I gave you some good ideas for the case n=10 which can be generalized for bigger n.