in hindsight, in an implementation I'd

• prepare multiplication tables of the chosen i with all remaining digits
• use sieves to find remaining digits, multiplication and summing results
• realize these different sieves as bit strings. like $remaining = vec(100100100) would represent only 3,6 and 9 as remaining possibilities
• obviously you must bound if $remaining is 0
• sieves as bit strings allow effective filtering of sets by and operations.
• applying a sieve to a carry would just mean shifting the string

==== for instance if you decide to go from left to right left with $i=4

i * efgh = abcd

the multiplication table would look like

  DB<14> $i=4; for $x (1..9) { next if $x==$i; $p = $i*$x; $C=int($p/1
+0); $S=$p%10;  print "$i * $x = $p \t$C $S\n" }
4 * 1 = 4       0 4
4 * 2 = 8       0 8
4 * 3 = 12      1 2
4 * 5 = 20      2 0
4 * 6 = 24      2 4
4 * 7 = 28      2 8
4 * 8 = 32      3 2
4 * 9 = 36      3 6
[download]

#                                 987654321
@carry0 = (1,2)   , $carry0 =        vec(11)
@carry1 = (3)     , $carry1 =      vec(0100) 
@carry2 = (5,6,7) , $carry2 =   vec(1110000) 
@carry3 = (8,9)   , $carry3 = vec(110000000)
[download]

( update when going from left to right you have to also put 7 into @carry3, because 28 could add to a former carry. going from right to left is indeed easier ...)

==== after trying $e=1 you know that

@remaing=(2,3,5,6,7,8,9) => $remaining = vec(111110110)

$a = $i*$e + carry(4*f) = 4*1 + range(0..3)

the carry range filter for 0..3 is vec(1111) shifted accordingly for 4 is $carryrange=vec(1111000)

$remaining & $carryrange = vec(1110000) => possible $a are in (5,6,7)

=> carry=0 is (obviously) forbidden $remaining & ($carry1 | $carry2 | $carry3) = vec(111110100) => possible $f are in (9,8,7,6,5,3)

using this approach has several advantages

• set operations cut down possible branches before they happen (NB: sub calls are expensive in Perl)
• set operations as bit string operations are very fast
• after preparing the multiplication table, you'll practically never need to add or multiply any more, all operations happen as "shifts", "ands" and "ors" on bit-strings
• these operations happen in "parallel", they sieve on all set-members
• this scales well for higher bases, you can still handle a 33-base in a 32-bit integer (I doubt you want to go higher)
• you can generalize this approach for similar problems (integer fraction puzzles)

this approach will lead to a very efficient branch and bound already, I'm confident you can find even more "filter rules" to bound more efficiently.

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.