notes.html
problem 43 · 24 lines
<article>
<h3>Problem Analysis</h3>
<p>
A <a class="reference-source" href="https://en.wikipedia.org/wiki/Pandigital_number" rel="noopener noreferrer" target="_blank">pandigital number</a> over the digits 0 to 9 is a ten-digit arrangement that uses each digit exactly once. There are 10! = 3,628,800 such arrangements, since each is a <a class="reference-source" href="https://en.wikipedia.org/wiki/Permutation" rel="noopener noreferrer" target="_blank">permutation</a> of the ten digits. The brute-force route would generate every permutation and test each against the seven divisibility rules. That is computationally feasible but profoundly wasteful: nearly every permutation fails the first constraint, so almost all of the work is discarded immediately.
</p>
<p>
The structural insight that makes this problem genuinely easy is that the seven three-digit windows <em>overlap by two digits</em>. The window <code>d2 d3 d4</code> shares <code>d3 d4</code> with <code>d3 d4 d5</code>, which shares <code>d4 d5</code> with <code>d4 d5 d6</code>, and so on down to <code>d8 d9 d10</code>. Whenever constraints share variables, they can be propagated: once I fix one window, the adjacent window is almost completely determined - only one new digit is free, and it must simultaneously satisfy a divisibility rule and avoid repeating any digit already placed. This reduces the search from an exhaustive scan of permutations to a narrow <a class="reference-source" href="https://en.wikipedia.org/wiki/Backtracking" rel="noopener noreferrer" target="_blank">backtracking</a> walk with aggressive <a class="reference-source" href="https://en.wikipedia.org/wiki/Constraint_propagation" rel="noopener noreferrer" target="_blank">constraint propagation</a>. The worst-case asymptotic bound is still O(10!), but the real cost collapses to a few thousand node visits, completing in microseconds. The first digit <code>d1</code> carries no divisibility constraint at all, so it is simply whichever digit remains unused once the other nine positions are settled.
</p>
<h3>Solution Approach</h3>
<h4>Right-to-left Constrained Backtracking over the Divisor Chain</h4>
<p>
Both the C file and the Python file implement the same algorithm and differ only in language idiom. The core is a recursive descent over the divisor chain 17 -> 13 -> 11 -> 7 -> 5 -> 3 -> 2, building the number from right to left one digit at a time.
</p>
<p>
I seed the search with a precomputed constant table of the 44 valid three-digit multiples of 17 that have no repeated digit (such as <code>"017"</code>, <code>"289"</code>, <code>"986"</code>). These are exactly the legal values for the rightmost window <code>d8 d9 d10</code>. Starting from this table eliminates one full recursion level and makes the entry conditions explicit: I have already discharged the divisibility-by-17 constraint before recursion even begins.
</p>
<p>
From each seed I call the recursive generator with the current partial string and the next divisor to satisfy. At each step I iterate over the digits <code>'0'</code> through <code>'9'</code>, skip any digit already present in the partial string, prepend the candidate, and check whether the leading three characters of the new string are divisible by the current divisor. If they are not, I prune that branch immediately. If they are, I recurse with the next divisor in the chain. When the chain is exhausted (after satisfying 2), the partial string holds positions <code>d2</code> through <code>d10</code>; I locate the single unused digit, prepend it as <code>d1</code>, convert the ten-character string to an integer, and accumulate it.
</p>
<p>
I chose to build right to left rather than left to right because the divisibility window always sits at the first three characters of the partial string. Prepending keeps the validation at a fixed offset, so the index arithmetic never changes as the string grows - this removes a whole class of off-by-one errors. The C version encodes the divisor transition in a <code>switch</code> statement (<code>next_divisor</code>) and accumulates into a global <code>total_sum</code> using a fixed-size character buffer and <code>memcpy</code>, so it never touches the heap. The Python version expresses the same transition as a dictionary lookup and uses <code>yield from</code> recursion, so the top-level aggregation consumes results lazily. Functionally they are identical; the C avoids allocation entirely, while the Python reads more declaratively.
</p>
</article>