Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 

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     '
		,@FromTableorString	TINYINT = 1 --1 = run from TC63, else run from Input Parm
 
DECLARE @SudTable	TABLE (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     '
		,@FromTableorString	TINYINT = 1 --1 = run from TC63, else run from Input Parm
 
DECLARE @SudTable	TABLE (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.

Comments

Posted by jacob sebastian on 1 December 2011

Congratulations Jason!

Posted by Bob Cullen on 1 December 2011

Hi Jason - I, too, like Sudoku, but have never thought of using T-SQL to solve it. Well done !!

What I find more interesting than solving an existing puzzle is the process by which the part-populated grid is prepared in the first place, especially setting out with the intent of making it Easy, Difficult, Fiendish or whatever to solve.

Any ideas about how this is done?

Bob

Posted by Carla Wilson on 1 December 2011

Congratulations!

I can't read your solution yet, because I have been meaning to work on this challenge (obviously not to submit). ;)

Like Bob, I also have toyed with how one might generate a puzzle.

Posted by Jason Brimhall on 1 December 2011

@jacob - Thank you.  Great concept you have going.

Posted by Jason Brimhall on 1 December 2011

@Bob and @Carla

Thanks.  I have not thought of a TSQL Solution to generate a puzzle.  That would be fun.

Leave a Comment

Please register or log in to leave a comment.