Fun with SQL: Solve Sudoku with recursive SQL
Solve Sudoku using SQL!!! This festive season, impress your friends and colleague with your quick Sudoku skills and some clever SQL!
How? Using recursive SQL, one can “solve” Sudoku. Just one SQL statement! Amazing. I think it is pretty fun!
The SQL below works in both Db2 z/OS and Db2 LUW.
- The SQL should be able to run in any RDBMS with little modification.
The SQL statement only uses SYSDUMMY1 as the initial driver. The original Sudoku puzzle is entered as one long string of 81 characters with digits of 1-9 to represent the values in the known squares and using a “.” (period) to represent the unknown squares.
The solution below enters the string in the visual format of 9 lines of 9 characters/squares. The 9 lines are concatenated together (easier to enter/read).
The solution below produces a final result to show both the original input Sudoku and the final solved Sudoku. The result set is display in two 9x9 grids to make it easy to read. Bars and dashes are used to make it look like traditional Sudoku from your newspaper or what-not. And yes, I will grant you that the SQL convulsions to produce a pretty result set are arbitrarily excessive. But when I use SQL, I really try to avoid the use other tools or steps for formatting readable result sets. I like to do everything in SQL. If you want to skip all the formatting, just uncomment the SQL at the line of “UNCOMMENT TO SEE FINAL ANSWER”.
Full disclosure: I discovered this SQL solution for SUDOKO by attending Martin Hubel’s Db2 Night Show in February 2021. The presentation was called “Some Iterations Over Recursion” by Michael Tiefenbacher. Among other useful things, the presentation showed the SQL solution that was the basis for my SQL below. The presentation can be downloaded from the Db2 night show website or IDUG website for past conferences. The original Sudoku SQL from the presentation is available from Henrick Loeser. Thanks to all of them! The true origin of the SQL is lost in time, although “the google” did help me find variations of this SQL back from 2009 (Anton Scheffer).
- Presentation: Some iterations Over Recursion (from Db2 nightshow):
- Replay of presentation from Db2 Nightshow:
- GITHUB link to SQL from Henrick Loeser:
- Another version of the presentation is from IDUG EMEA 2018 (and IDUG NA 2019):
Try the SQL!
You should be able to cut&paste and let it run! It should work. Let me know what you think!
WITH CTE_ORIG(sud) AS ( /* INPUT SUDOKO AS ONE 81 CHAR STRING = 9X9 */
/* SHOW STRING HERE AS 9 STRINGS OF 9 CHAR */
/* > SHOWING INPUT STRING AS 9X9 MAKES IT EASIER TO VISUALIZE */
SELECT ('91.7.....'
||'.326.9.8.'
||'..7.8.9..'
||'.86.3.17.'
||'3.......6'
||'.51.2.84.'
||'..9.5.3..'
||'.2.3.149.'
||'.....2.61')
-- SELECT ('..2....13'
-- ||'.1493....'
-- ||'..8.4....'
-- ||'1..2..9..'
-- ||'6..4..2.8'
-- ||'2..68....'
-- ||'8....9641'
-- ||'47...6...'
-- ||'.5..1.8.2')
FROM SYSIBM.SYSDUMMY1
)
, CTE_DIGITS(z, lp) AS ( /* WE NEED A CTE WITH 9 ROWS FOR NBRS 1 TO 9 */
/* use recursion to build THIS little CTE ! */
SELECT '1' as z, 1 as lp from sysibm.sysdummy1
UNION ALL
SELECT CAST(lp+1 AS varchar(1)), lp+1 FROM CTE_DIGITS WHERE lp < 9
)
/********************************************************************/
, CTE_X(s, ind) AS ( /* HERE IS THE (MAGIC) RECURSIVE MATH !!!! */
SELECT sud, LOCATE_IN_STRING(sud, '.') FROM CTE_ORIG
UNION ALL
SELECT
substr(s, 1, ind-1) || z || substr(s, ind+1)
,LOCATE_IN_STRING(substr(s, 1, ind-1)|| z || substr(s, ind+1), '.')
FROM CTE_X, CTE_DIGITS AS z
WHERE ind>0
AND NOT EXISTS (
SELECT 1
FROM CTE_DIGITS AS lp
WHERE z.z = substr(s, ((ind-1)/9)*9 + lp, 1)
OR z.z = substr(s, (mod((ind-1), 9)) + (lp-1)*9 + 1, 1)
OR z.z = substr(s, (mod(((ind-1)/3), 3)) * 3
+ ((ind-1)/27) * 27 + lp
+ ((lp-1) / 3) * 6, 1)
)
)
/********************************************************************/
--select * from CTE_X; -- UNCOMMENT THIS TO SEE ANSWER(S)!
--SELECT S FROM CTE_X WHERE ind=0; -- UNCOMMENT TO SEE FINAL ANSWER
, CTE_ANSWER AS ( /* THE LAST ROW OF THE CTE_X HAS THE FINAL ANSWER! */
SELECT S FROM CTE_X WHERE ind=0
)
/**********************************************************************/
/* FORMAT OUTPUT TO BE PRETTY *****************************************/
, cte_both as ( /* GO THROUGH ORIG AND ANSWER > EACH 9 TIMES
AND PARSE INTO BLOCKS OF 9 WIDE*/
SELECT SUBSTR(Sud,(LP-1)*9+1,9) as s9, lp*10 as l
FROM CTE_DIGITS, CTE_ORIG
union all
SELECT SUBSTR(S,(LP-1)*9+1,9) as s9, (lp+9)*10 as l
FROM CTE_DIGITS, CTE_ANSWER
)
, cte_f as ( /* GO THROUGH BOTH ANSWERS AND FORMAT PRETTY */
select '|'||substr(s9,1,3)||'|' /* SPLIT EACH LINE AND PUT BARS */
||substr(s9,4,3)||'|'
||substr(s9,7,3)||'|' as sf
, l
from cte_both
union all
select /* ADD SEPERATOR LINES in location of line L */
'-------------' AS SF
, CASE WHEN LP=9 THEN 99 ELSE ((LP-2)*30+5) END AS L
from CTE_DIGITS
)
select sf AS SUDOKO_Q_A --,l /* select result with pretty formatting */
from cte_f
order by l
;
SUDOKO_Q_A
-------------
-------------
-------------
|91.|7..|...|
|.32|6.9|.8.|
|..7|.8.|9..|
-------------
|.86|.3.|17.|
|3..|...|..6|
|.51|.2.|84.|
-------------
|..9|.5.|3..|
|.2.|3.1|49.|
|...|..2|.61|
-------------
-------------
|918|745|632|
|532|619|784|
|647|283|915|
-------------
|286|534|179|
|394|178|256|
|751|926|843|
-------------
|169|457|328|
|825|361|497|
|473|892|561|
-------------