All right, so here's my take on Encsé's infamous 9 Digit Problem. Let's first recap what the problem statement was:

Find a number consisting of 9 digits in which each of the digits from 1 to 9 appears only once. This number must also satisfy these divisibility requirements:

1. The number should be divisible by 9.
2. If the rightmost digit is removed, the remaining number should be divisible by 8.
3. If the rightmost digit of the new number is removed, the remaining number should be divisible by 7.
4. And so on, until there’s only one digit (which will necessarily be divisible by 1).

Power of transformations - XSLT and CL1

The XSLT and CL1 solutions are both based on the following algorithm:

1. (level zero) Initialize the candidate set with an empty number (empty string if you will).
2. (level i) Extend all currrent candidates with each of the possible remaining digits.
3. Check if divisibility is met for each of the resulting to-be-candidates
4. Accept those that met the criteria, reject all others
5. If we have candidates that are 9 digit long, then that's the solution to the original puzzle. Otherwise go to step 2 and iterate over the new set of candidates (level i+1).

The basic idea is to represent each level in the above algorithm by a transformation step. That is, the ith step in the transformation pipe will contain the candidates of length i. For convenience, we record the remaning possible digits for each candidate that they carry over to the next transformation step.

That's it. The CL1 solution is available as a sample program to the IDW. I have reworked it somewhat to make it more intentional and Cactus-proof. :) Check out the ISC support site for details.

The XSLT solution is available at Encsé's site. There are a couple of interesting things to note about the XSLT code:

• The pipeline is implemented fully in xslt, using a well-known trick that involves parsing back the result of the previous transformation step via the node-set function.
• To make the code self-sufficient the xslt file itself serves as its own input. The initial transformation step makes sure that we have a proper initial state to start from.

Hurray for Spreadsheets

My Excel solution is based on the backtracking variant of the above algorithm. That is, we take one number at a time, try to extend and backtrack if it's not successful. The first row of the spreadsheet gives some clues - in Hungarian notation (sorry about that). The key is the formula for column C (irowParentRel) which drives the whole calculation.

Try for yourself, delete all but the first three rows, and then copy down the third row as long as you have some meaningful results (a bit more than 1600 rows needed). Solutions are marked in the fSolution column plus their row is highlighted in yellow.

More to come...

I'm pretty determined to create a Brainfuck implementation. For that, however, I'll first need to create a Brainfuck Workbench that will make it less painful to write programs in Brainfuck. Some might think that it spoils the fun, but I think it will actually be a lot of fun writing the Workbench itself so the fun level will balance out nicely in the end. And I think it will make the world a better place.

A solution in Ant (or Make) would also be nice. And have you heard about Wierd or Chef? Those should be fun! Well, one of these days...