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.