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.
