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
# 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)
( 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.
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.