How to solve the 123456789 Equation Puzzle in SQL
May 30th, 2008 By Frank Zhou
The following is an interesting puzzle posted by Usenet rec-puzzles.org archive:
In how many ways can “.” be replaced with “+”, “-”, or “” (concatenate) in .1.2.3.4.5.6.7.8.9 = 1 to form a correct equation?
——————————————-SQL Solution————————-
SELECT str_eq || ' = ' || output as output, count(*) over ( ) as counter
FROM
(select str_eq, XMLQuery( str_eq RETURNING CONTENT).getnumberval() output
FROM
(
WITH DATA AS
(
SELECT doc.extract('/l/text()').getStringVal() chars
FROM
TABLE(xmlSequence(extract(XMLType('<doc><l>'||
replace('+,-, ',',','</l><l>')||'</l></doc>'),'/doc/l'))) doc
)
SELECT replace(sys_connect_by_path(chars||to_char(LEVEL),'.'), '.') as str_eq
FROM ( SELECT chars from data)
WHERE LEVEL = 9
CONNECT BY LEVEL <= 9
)
)
where output = 1;
OUTPUT COUNTER
-------------------------------------- ----------
+1+2+3+4+5-6-7+8-9 = 1 69
+1+2+3+4-5+6+7-8-9 = 1 69
+1+2+3+45-67+8+9 = 1 69
+1+2+3-4-5-6-7+8+9 = 1 69
+1+2-3+4-5-6+7-8+9 = 1 69
+1+2-3-4+5+6-7-8+9 = 1 69
+1+2-3-4+5-6+7+8-9 = 1 69
+1+2-34+56-7-8-9 = 1 69
+1+23+4-5+67-89 = 1 69
+1+23+45-67+8-9 = 1 69
+1+23-4-5-6-7+8-9 = 1 69
OUTPUT COUNTER
-------------------------------------- ----------
+1+23-45-67+89 = 1 69
+1-2+3+4-5+6-7-8+9 = 1 69
+1-2+3+4-5-6+7+8-9 = 1 69
+1-2+3-4+5+6-7+8-9 = 1 69
+1-2+34-56+7+8+9 = 1 69
+1-2-3+4+5+6+7-8-9 = 1 69
+1-2-3-4+5-6-7+8+9 = 1 69
+1-2-3-4-5+6+7-8+9 = 1 69
+1-2-3-45+67-8-9 = 1 69
+1-23+4+5+6+7-8+9 = 1 69
+1-23+45+67-89 = 1 69
OUTPUT COUNTER
-------------------------------------- ----------
+1-23-4+5-67+89 = 1 69
+1-23-45+67-8+9 = 1 69
+12+34+5-67+8+9 = 1 69
+12-34+5-6+7+8+9 = 1 69
-1+2+3+4+5-6-7-8+9 = 1 69
-1+2+3+4-5+6-7+8-9 = 1 69
-1+2+3-4+5+6+7-8-9 = 1 69
-1+2-3+4-5-6-7+8+9 = 1 69
-1+2-3-4+5-6+7-8+9 = 1 69
-1+2-3-4-5+6+7+8-9 = 1 69
-1+23+4+5-6-7-8-9 = 1 69
OUTPUT COUNTER
-------------------------------------- ----------
-1+23+45-67-8+9 = 1 69
-1+23-4+5+67-89 = 1 69
-1+23-4-5-6-7-8+9 = 1 69
-1-2+3+4-5-6+7-8+9 = 1 69
-1-2+3-4+5+6-7-8+9 = 1 69
-1-2+3-4+5-6+7+8-9 = 1 69
-1-2-3+4+5+6-7+8-9 = 1 69
-1-2-3-4-5+6-7+8+9 = 1 69
-1-23+4+5+6-7+8+9 = 1 69
-12+34-5-6+7-8-9 = 1 69
1+2+3+4+5-6-7+8-9 = 1 69
OUTPUT COUNTER
-------------------------------------- ----------
1+2+3+4-5+6+7-8-9 = 1 69
1+2+3+45-67+8+9 = 1 69
1+2+3-4-5-6-7+8+9 = 1 69
1+2-3+4-5-6+7-8+9 = 1 69
1+2-3-4+5+6-7-8+9 = 1 69
1+2-3-4+5-6+7+8-9 = 1 69
1+2-34+56-7-8-9 = 1 69
1+23+4-5+67-89 = 1 69
1+23+45-67+8-9 = 1 69
1+23-4-5-6-7+8-9 = 1 69
1+23-45-67+89 = 1 69
OUTPUT COUNTER
-------------------------------------- ----------
1-2+3+4-5+6-7-8+9 = 1 69
1-2+3+4-5-6+7+8-9 = 1 69
1-2+3-4+5+6-7+8-9 = 1 69
1-2+34-56+7+8+9 = 1 69
1-2-3+4+5+6+7-8-9 = 1 69
1-2-3-4+5-6-7+8+9 = 1 69
1-2-3-4-5+6+7-8+9 = 1 69
1-2-3-45+67-8-9 = 1 69
1-23+4+5+6+7-8+9 = 1 69
1-23+45+67-89 = 1 69
1-23-4+5-67+89 = 1 69
OUTPUT COUNTER
-------------------------------------- ----------
1-23-45+67-8+9 = 1 69
12+34+5-67+8+9 = 1 69
12-34+5-6+7+8+9 = 1 69
69 rows selected.
June 25th, 2010 at 11:20 am
11GR2: WITH n AS (SELECT ROWNUM-1 rn FROM DUAL CONNECT BY ROWNUM<=10) ,o AS (SELECT '+' op FROM DUAL UNION ALL SELECT '-' op FROM DUAL UNION ALL SELECT NULL FROM DUAL) ,t(num,tot,expr,op) AS ( SELECT 0 as num, 0 as tot, '' AS expr, '' AS op FROM DUAL UNION ALL SELECT n.rn ,DECODE(o.op,'+',t.tot+n.rn,'-',t.tot-n.rn,DECODE(t.op,'+',t.tot-t.num+t.num*10+n.rn,t.tot+t.num-t.num*10-n.rn)) ,t.expr||o.op||n.rn ,o.op FROM n,t,o WHERE t.num = n.rn-1 AND (o.op IS NOT NULL OR t.op IS NOT NULL) ) SELECT expr||'='||tot AS OUTPUT FROM t WHERE num=9 AND tot=1; other solutions wihtout recursive WITH: WITH t AS( SELECT '+' X FROM DUAL UNION ALL SELECT '-' X FROM DUAL UNION ALL SELECT '' X FROM DUAL) ,t2 AS ( SELECT * FROM (SELECT ROWNUM id,t.x|| 1||t1.x|| 2||t2.x|| 3||t3.x|| 4||t4.x|| 5||t5.x|| 6||t6.x|| 7||t7.x|| 8||t8.x|| 9 y FROM t,t t1,t t2,t t3,t t4,t t5,t t6,t t7,t t8 WHERE t.x IN ('-','+') ) WHERE REPLACE(y,123)=y AND REPLACE(y,234)=y AND REPLACE(y,345)=y AND REPLACE(y,456)=y AND REPLACE(y,567)=y AND REPLACE(y,678)=y AND REPLACE(y,789)=y ) SELECT LTRIM(y,'+') FROM (SELECT id,y,REGEXP_SUBSTR(y,'[+-]',1,rn) op,REGEXP_SUBSTR(y,'[^+-]+',1,rn) num FROM t2,(SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=9) ) GROUP BY id,y HAVING SUM(DECODE(op,'+',num,-num))=1 ; WITH t AS( SELECT n,op FROM (SELECT '+' op FROM DUAL UNION ALL SELECT '-' op FROM DUAL UNION ALL SELECT '' op FROM DUAL) ,(SELECT ROWNUM n FROM DUAL CONNECT BY ROWNUM<=9) WHERE n>1 OR op IN ('+','-') ) ,t2 AS ( SELECT ROWNUM id, REPLACE(SYS_CONNECT_BY_PATH(op||n,'@'),'@') y FROM t WHERE n=9 START WITH n=1 CONNECT BY n= PRIOR n+1 AND (op IS NOT NULL OR PRIOR op IS NOT NULL) ) SELECT LTRIM(y,'+') FROM (SELECT id,y,REGEXP_SUBSTR(y,'[+-]',1,rn) op,REGEXP_SUBSTR(y,'[^+-]+',1,rn) num FROM t2,(SELECT ROWNUM rn FROM DUAL CONNECT BY ROWNUM<=9) ) GROUP BY id,y HAVING SUM(DECODE(op,'+',num,-num))=1 ; WITH t AS( SELECT n,op FROM (SELECT '+' op FROM DUAL UNION ALL SELECT '-' op FROM DUAL UNION ALL SELECT '~' op FROM DUAL) ,(SELECT ROWNUM n FROM DUAL CONNECT BY ROWNUM<=9) WHERE n>1 OR op IN ('+','-') ) ,t2 AS ( SELECT ROWNUM id, REPLACE(SYS_CONNECT_BY_PATH(op||n,'@'),'@') y ,DECODE(op,'+',n,'-',-n,DECODE(PRIOR op,'+',- (PRIOR n)+ (PRIOR n)*10 +n, (PRIOR n)- (PRIOR n)*10 -n)) val FROM t WHERE n=9 START WITH n=1 CONNECT BY n= PRIOR n+1 AND (op <>'~' OR PRIOR op <>'~') ) SELECT LTRIM(REPLACE(t2.y,'~'),'+') FROM t2,(SELECT ROWNUM n FROM DUAL CONNECT BY ROWNUM<=9) GROUP BY t2.y HAVING SUM(DECODE(SUBSTR(y,(n-1)*2+1,1),'+',n,'-',-n,DECODE(SUBSTR(y,(n-2)*2+1,1),'+',-(n-1)+(n-1)*10+n,(n-1)-(n-1)*10-n )))=1;