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.

[codesyntax lang=”tsql”]

--
--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

[/codesyntax]

 

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.

[codesyntax lang=”tsql”]

--
--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

[/codesyntax]

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.

Original post (opens in new tab)
View comments in original post (opens in new tab)

Rate

You rated this post out of 5. Change rating

Share

Share

Rate

You rated this post out of 5. Change rating