TSQL Sudoku

Comments: 8 Comments
Published on: August 17, 2011

I am a big Sudoku fan.  Typically if I need a break, I will break out a Sudoku puzzle from any of a number of different sources (Websudoku, Android Apps, Puzzle Books).  Over time, I have come across a solution here or there to solve these puzzles via TSQL.

There are a few of these solutions out there already, such as one by Itzik Ben-Gan (which I can’t get to download without the file corrupting so I still haven’t seen it), or this one on SSC (which works most of the time but does provide inaccurate results from time to time).  I still wanted something to do this via CTE (much like the solution by Itzik is described to be at the link provided – if you have that code, I want to SEE it).

Just a couple of years ago, there was a post at SSC asking for some help converting a solution from Oracle to TSQL.  I checked out that code and worked on it for a day or two.  Then I got busy with other work that replaced the pet project.  I hadn’t given the idea much thought until just a few days ago as I was browsing my Topic list I had been building for articles.

This solution stuck with me this time around and I wanted to finish it up.  The Oracle solution for whatever reason made a lot more sense to me this time around, and I made great progress quickly.  It was actually this project that I was working on that prompted another post.  While working through the solution, I learned a fair amount about both flavors of SQL.  So, in preface to continuing to read here, you may want to check out the other article real quick since it pertains to some of the conversions done in this project.

Problems First

The OP supplied the Oracle solution asking for help in creating a TSQL Solution.  Here is that Oracle version.

WITH x( s, ind ) AS
( SELECT sud, instr( sud, ' ' )
  FROM ( SELECT '53  7    6  195    98    6 8   6   34  8 3  17   2   6 6    28    419  5    8  79' sud FROM dual )
  UNION ALL
  SELECT substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 )
       , instr( s, ' ', ind + 1 )
  FROM x
     , ( SELECT to_char( rownum ) z
         FROM dual
         connect BY rownum <= 9
       ) z
  WHERE ind > 0
  AND NOT EXISTS ( SELECT NULL
                   FROM ( SELECT rownum lp
                          FROM dual
                          connect BY rownum <= 9
                        )
                   WHERE z = substr( s, trunc( ( ind - 1 ) / 9 ) * 9 + lp, 1 )
                   OR    z = substr( s, mod( ind - 1, 9 ) - 8 + lp * 9, 1 )
                   OR    z = substr( s, mod( trunc( ( ind - 1 ) / 3 ), 3 ) * 3
                                      + trunc( ( ind - 1 ) / 27 ) * 27 + lp
                                      + trunc( ( lp - 1 ) / 3 ) * 6
                                   , 1 )
                 )
)
SELECT s
FROM x
WHERE ind = 0
/

If you read that other post I mentioned, you will quickly identify 5 functions/objects in use in this script that just don’t work in TSQL.  Those are:  dual, instr, substr, connect by, and trunc.  I did not mention mod in my other post, but mod is also done differently in TSQL than in Oracle.  I thought this one was a bit obvious and stuck with the top 5 ;) .

Solution

After figuring out some of the subtle differences between commands and the best way to approach this, I was able to come up with a TSQL solution that works.  Take not first of that last where clause in the CTE of the Oracle solution.  That clause is very similar to what I refer to as the train-stop method to get unique paths in a hierarchy.  There are several methods to do similar functionality – I have concatenated strings with Stuff as wells cast to produce this functionality.

So here goes with the first rendition of this query.

DECLARE @SudokuGivens VARCHAR(100)
SET @SudokuGivens = '53  7    6  195    98    6 8   6   34  8 3  17   2   6 6    28    419  5    8  79'
;
WITH
      E1(N) AS ( --=== Create Ten 1's
                 SELECT 1 UNION ALL SELECT 1 UNION ALL
                 SELECT 1 UNION ALL SELECT 1 UNION ALL
                 SELECT 1 UNION ALL SELECT 1 UNION ALL
                 SELECT 1 UNION ALL SELECT 1 UNION ALL
                 SELECT 1 UNION ALL SELECT 1 --10
               )
,dual(N) AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT N)) FROM E1)
,x( s, ind ) AS
( SELECT CONVERT(VARCHAR(100),sud), CHARINDEX(' ',Ss.sud ) AS ind
	FROM 
		( SELECT @SudokuGivens AS sud FROM dual ) Ss
  UNION all
  SELECT CONVERT(VARCHAR(100),SUBSTRING( s, 1, ind - 1 ) + z + SUBSTRING( s, ind + 1 ,LEN(s)))
       , CHARINDEX( ' ', s, ind + 1 ) AS ind
  FROM x
    CROSS APPLY ( SELECT CONVERT(VARCHAR(25), N ) z
         FROM dual
         WHERE N <= 9
       ) z
  WHERE ind > 0
  and not exists ( SELECT null
                   FROM ( SELECT N AS lp
                          FROM dual
                          WHERE N <= 9
                        ) ww
					WHERE z = SUBSTRING( s, ( ind - 1)% 9  - 8 + lp * 9, 1 )
						or    z = SUBSTRING( s, ( ( ind - 1 ) / 9 ) * 9 + lp, 1 )
						or    z = SUBSTRING( s, (( ( ind - 1 ) / 3 )%3) * 3
                                      + ( ( ind - 1 ) / 27 ) * 27 + lp
                                      + ( ( lp - 1 ) / 3 ) * 6
                                   , 1 )
                 )
)
SELECT DISTINCT s
	FROM x
	WHERE ind = 0

Notice that I have chosen to use an Itzik style numbers table/CTE.  This functions as my “dual” table translation and is necessary in the remainder of the query.  The final where clause of the CTE is simplified in TSQL by simply removing the TRUNC commands.  The original solution was merely removing the decimal precision.  In TSQL, the conversion is done to INT implicitly in this case.  I need to test a few more cases, but so far it works without error.

What this does not do…

This is the first rendition of the script.  Currently, it only returns the number sequence in one big long string.  I am working on modifying this script to produce a grid layout with the solution.  I envision this will require the use of PIVOT and possibly UNPIVOT to get me close.  In addition, I expect that further string manipulation will be needed – such as stuffing commas and then splitting it to make the PIVOT/UNPIVOT easier.  I’ll have to try some things and figure it out.  Also, I expect that some explicit conversions may be best in this query.  That could help improve performance a tad.

This, to this point, has been a fun diversion.  This has helped to learn a bit about Oracle, hierarchies, and to do a little math – all in one.  Better yet is that there is still work to be done on it and more learning.  If you have ideas how to make it better – I am very interested.

8 Comments - Leave a comment
  1. This is awesome.
    SQL vs. Sudoku was one of the first blog posts I ever wrote: http://michaeljswart.com/2008/04/sudoku-vs-sql/

    If you look at the solution, you’ll notice a few things. It’s very SQL 2000-ish.
    And it uses savepoints for flow control.

    But absolutely a fun diversion!

  2. Hmm, it doesn’t seem to work on this puzzle:
    SET @SudokuGivens = ‘ 15 6 7 9 4 5 1 9 4 8 3 6 2 7 8 7 35 ‘
    I cancelled the query after 30 minutes. I think the big difference here is the number of givens. My puzzle has 19 givens vs. 30 givens in the other puzzle.

    • Jason Brimhall says:

      I will need to work on that. I think it is a performance optimization of the script that is needed. It could also very well be a need for a physical numbers table that is well indexed.

  3. (Shoot, the last comment replaced whitespace with a single space. Here’s the puzzle I meant:
    ‘..15…….6…..7….9..4…5…1..9…4…8..3…6…2..7….8…..7…….35..’
    after replacing ‘.’ with ‘ ‘)

    • Jason Brimhall says:

      K. I ran that same string on my laptop and got results back after 12 min. It produced accurate results, but 12 min is still slow. Granted, that is a lot of permutations and one may not solve that sudoku faster than 12 min without a computer – it needs optimized.

  4. Jason Brimhall says:

    updated version coming soon – perf tuned

  5. quoted on TSQL Sudoku | SQL RNNR says:

    [...] TSQL Sudoku II August 23, 2011 Jason Brimhall No comments As luck would have it, today I came across this TSQL Challenge.  It just so happens that I had already worked on a SQL Sudoku script and blogged about it less than one week ago – here. [...]

Leave a comment

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>






Calendar
August 2011
M T W T F S S
« Jul   Sep »
1234567
891011121314
15161718192021
22232425262728
293031  
Content
SQLHelp

SQLHelp


Welcome , today is Wednesday, April 23, 2014