Blog Post

TSQL Challenge 63 – Update

,

If you recall, I like Sudoku.  I even posted a script for solving it via TSQL.  I went so far as to enter my script into a TSQL Challenge.  That all started way back in August.  Today, I have an update!!

I was notified this morning from BeyondRelational.com that I have earned a new badge.  Cool, what’s the badge?  I clicked the link and it took me to this badge.

Huh?  I’m a winner of the SQL Sudoku Challenge?  Awesome!

Looking it over, I am winner #3.  This means I could have done better with my solution.   And looking at the other solution stats, it appears I will need to find time to see what the others did to make their solutions go sooooo fast.  I have some learning to do – woohoo.

So, now that means I need to post my solution.

--
--These Variables are intended to be used as input parameters if made into a proc.
DECLARE @SudokuNo INT = 3 --my script is setup to allow the table to contain multiple puzzles.
,@SudokuGivens VARCHAR(100) = '53  7    6  195    98    6 8   6   34  8 3  17   2   6 6    28    419  5    8  79'
--'  15       6     7    9  4   5   1  9   4   8  3   6   2  7    8     7       35  '
--'   9 1   6     5            7 2   1        29    3    4   6 7 55     8     1     '
,@FromTableorStringTINYINT = 1 --1 = run from TC63, else run from Input Parm
 
DECLARE @SudTableTABLE (RowCol INT PRIMARY KEY CLUSTERED, ConcatRow VARCHAR(10))
 
IF @FromTableorString = 1
BEGIN
--Populate Data for missing vectors (Col/Row) with A space
--Use an Isnull and Outer Apply in case there are no givens for a particular row.
WITH dual(N) AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT N)) FROM ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) x(N)
),rowcols AS (SELECT DISTINCT ROW.N AS ROW,Col.N AS Col FROM Dual ROW Cross Apply Dual Col)
 
--Concatenate into a string if the SudokuSource is a Table
SELECT @SudokuGivens = (SELECT  Isnull(t.DATA,0)
FROM TC63 T
RIGHT Outer Join rowcols D
ON D.ROW = T.ROW
And D.Col = T.Col
And SudokuNo = @SudokuNo
FOR xml PATH(''))  
 
END
SELECT @SudokuGivens = REPLACE(@SudokuGivens,'0',' ') --If from table, replace commas.  From a String can have spaces or commas
 
--Solve the Sudoku - into a string
;WITH x( s, ind ) AS
( SELECT @SudokuGivens, CHARINDEX(' ',@SudokuGivens ) AS ind
  UNION all
  SELECT CONVERT(VARCHAR(100),SUBSTRING( s, 1, ind - 1 ) + CONVERT(CHAR(1),z) + SUBSTRING( s, ind + 1 ,81))
       , CHARINDEX(' ', s, ind + 1 ) AS ind
  FROM x
    CROSS APPLY ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) z (z)
  WHERE ind > 0
  and not exists (SELECT null
FROM ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) ww (lp)
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 )
                 )
), Sud AS (
--Create a 9 record result set that has the string solution duplicated 9 times.  Then show only relevant 9 data for each row
SELECT TOP 9 SUBSTRING(s, ROW_NUMBER() OVER (ORDER BY s) * 9 - 8, ROW_NUMBER() OVER (ORDER BY s) * 9 - (ROW_NUMBER() OVER (ORDER BY s) * 9 - 9)) AS ConcatRow
FROM x
Cross Apply ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) y(N)
WHERE ind = 0
)
 
--Populate a Table Variable for further Row/Col manipulation
INSERT INTO @SudTable (RowCol,ConcatRow)
SELECT Row_Number() OVER (ORDER BY (SELECT 1)),ConcatRow
FROM Sud
 
--Pivot the data out to produce a 9x9 grid
SELECT @SudokuNo AS SudokuNo,c1.RowCol,[1],[2],[3],[4],[5],[6],[7],[8],[9]
FROM @SudTable S
Cross Apply (SELECT RowCol,[1],[2],[3],[4],[5],[6],[7],[8],[9]
FROM (SELECT S.RowCol
,ColNo = Row_Number() OVER (Partition BY RowCol ORDER BY ConcatRow)
,DATA = SUBSTRING(ConcatRow, ROW_NUMBER() OVER (Partition BY S.RowCol ORDER BY ConcatRow), 1)
FROM @SudTable S
Cross Apply ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) x(N)
) Intr
Pivot (
MAX(DATA)
FOR ColNo IN ([1],[2],[3],[4],[5],[6],[7],[8],[9])
) PVT) AS C1
WHERE c1.RowCol = S.RowCol
ORDER BY S.RowCol ASC

 

Sadly, that is not the most recent version of the script that I had.  I had intended on submitting this version, which is still slightly faster.

--
--These Variables are intended to be used as input parameters if made into a proc.
DECLARE @SudokuNo INT = 3 --my script is setup to allow the table to contain multiple puzzles.
,@SudokuGivens VARCHAR(100) = '53  7    6  195    98    6 8   6   34  8 3  17   2   6 6    28    419  5    8  79'
--'  15       6     7    9  4   5   1  9   4   8  3   6   2  7    8     7       35  '
--'   9 1   6     5            7 2   1        29    3    4   6 7 55     8     1     '
,@FromTableorStringTINYINT = 1 --1 = run from TC63, else run from Input Parm
 
DECLARE @SudTableTABLE (RowCol INT PRIMARY KEY CLUSTERED, ConcatRow VARCHAR(10))
 
IF @FromTableorString = 1
BEGIN
--Populate Data for missing vectors (Col/Row) with A space
--Use an Isnull and Outer Apply in case there are no givens for a particular row.
WITH dual(N) AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT N)) FROM ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) x(N)
),rowcols AS (SELECT DISTINCT ROW.N AS ROW,Col.N AS Col FROM Dual ROW Cross Apply Dual Col)
 
--Concatenate into a string if the SudokuSource is a Table
SELECT @SudokuGivens = (SELECT  Isnull(t.DATA,0)
FROM TC63 T
RIGHT Outer Join rowcols D
ON D.ROW = T.ROW
And D.Col = T.Col
And SudokuNo = @SudokuNo
FOR xml PATH(''))  
 
END
SELECT @SudokuGivens = REPLACE(@SudokuGivens,'0',' ') --If from table, replace commas.  From a String can have spaces or commas
 
--Solve the Sudoku - into a string
;WITH x( s, ind ) AS
( SELECT @SudokuGivens, CHARINDEX(' ',@SudokuGivens ) AS ind
  UNION all
  SELECT CONVERT(VARCHAR(100),SUBSTRING( s, 1, ind - 1 ) + CONVERT(CHAR(1),z) + SUBSTRING( s, ind + 1 ,81))
       , CHARINDEX(' ', s, ind + 1 ) AS ind
  FROM x
    CROSS APPLY ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) z (z)
  WHERE ind > 0
  and not exists (SELECT null
FROM ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) ww (lp)
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 )
                 )
), Sud AS (
--Create a 9 record result set that has the string solution duplicated 9 times.  Then show only relevant 9 data for each row
SELECT TOP 9 SUBSTRING(s, ROW_NUMBER() OVER (ORDER BY s) * 9 - 8, ROW_NUMBER() OVER (ORDER BY s) * 9 - (ROW_NUMBER() OVER (ORDER BY s) * 9 - 9)) AS ConcatRow
FROM x
Cross Apply ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) y(N)
WHERE ind = 0
)
 
--Populate a Table Variable for further Row/Col manipulation
INSERT INTO @SudTable (RowCol,ConcatRow)
SELECT Row_Number() OVER (ORDER BY (SELECT 1)),ConcatRow
FROM Sud
 
--Pivot the data out to produce a 9x9 grid
SELECT @SudokuNo AS SudokuNo,c1.RowCol,[1],[2],[3],[4],[5],[6],[7],[8],[9]
FROM @SudTable S
Cross Apply (SELECT RowCol,[1],[2],[3],[4],[5],[6],[7],[8],[9]
FROM (SELECT S.RowCol
,ColNo = Row_Number() OVER (Partition BY RowCol ORDER BY ConcatRow)
,DATA = SUBSTRING(ConcatRow, ROW_NUMBER() OVER (Partition BY S.RowCol ORDER BY ConcatRow), 1)
FROM @SudTable S
Cross Apply ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) x(N)
) Intr
Pivot (
MAX(DATA)
FOR ColNo IN ([1],[2],[3],[4],[5],[6],[7],[8],[9])
) PVT) AS C1
WHERE c1.RowCol = S.RowCol
ORDER BY S.RowCol ASC

Still, I am certain that (without having looked at the other winning solutions) this is not on par with the best solutions.  And I have a lot to learn.

Rate

You rated this post out of 5. Change rating

Share

Share

Rate

You rated this post out of 5. Change rating