-- Heres the equivalent SQL, as junctions have direct representation -- in Set Theory (see http://xrl.us/feh8)), then the below should be a -- very relevant way to express the problem, especially given -- MySQL/InnoDB (for one) already has the relevant logic to solve this -- problem in ~130ms on a 300MHz PII. Although of course that is -- still over 39,000,000 cycles! :-) Oracle took longer - ~6s, but -- admittedly it was only running on a dual processor 1.6GHz Opteron. -- Pg took a similar amount of time on a 1.7GHz AthlonXP (5s), SQLite -- took over 30s!

-- The `exhaustive' solution cranks through possibilities at about

-- MySQL table setup (adjust for your DBMS as necessary)

CREATE TABLE Dx ( X INTEGER(1) ); INSERT INTO Dx (X) VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9); CREATE TABLE Cx ( X INTEGER(1) ); INSERT INTO Cx (X) VALUES (0),(1);

-- actual query:

SELECT (S.X * 1000 + E.X * 100 + N.X * 10 + D.X) as SEND, (M.X * 1000 + Oh.X * 100 + R.X * 10 + E.X) as MORE, (M.X * 10000 + Oh.X * 1000 + N.X * 100 + E.X * 10 + Y.X) as MONEY from Dx M LEFT JOIN Dx S ON (M.X != S.X) LEFT JOIN Dx E ON ( (M.X != E.X) AND (S.X != E.X) ) LEFT JOIN Dx Oh ON ( (M.X !=Oh.X) AND (S.X !=Oh.X) AND (E.X !=Oh.X) ) LEFT JOIN Dx N ON ( (M.X != N.X) AND (S.X != N.X) AND (E.X != N.X) AND (Oh.X != N.X) ) LEFT JOIN Dx R ON ( (M.X != R.X) AND (S.X != R.X) AND (E.X != R.X) AND (Oh.X != R.X) AND (N.X != R.X) ) LEFT JOIN Dx D ON ( (M.X != D.X) AND (S.X != D.X) AND (E.X != D.X) AND (Oh.X != D.X) AND (N.X != D.X) AND (R.X != D.X) ) LEFT JOIN Dx Y ON ( (M.X != Y.X) AND (S.X != Y.X) AND (E.X != Y.X) AND (Oh.X != Y.X) AND (N.X != Y.X) AND (R.X != Y.X) AND (D.X != Y.X) ) LEFT JOIN Cx C0 ON ( C0.X = floor( (D.X + E.X) / 10 ) ) LEFT JOIN Cx C1 ON ( C1.X = floor( (N.X + R.X + C0.X) / 10 ) ) LEFT JOIN Cx C2 ON ( C2.X = floor( (E.X + Oh.X + C1.X) / 10 ) ) LEFT JOIN Cx C3 ON ( C3.X = floor( (S.X + M.X + C2.X) / 10 ) ) WHERE ( M.X != 0 ) AND ( S.X != 0 ) AND ( C3.X ) = M.X AND MOD( S.X + M.X + C2.X, 10) = Oh.X AND MOD( E.X +Oh.X + C1.X, 10) = N.X AND MOD( N.X + R.X + C0.X, 10) = E.X AND MOD( D.X + E.X , 10) = Y.X ;