August 18, 2011 at 9:31 am
Well, that is about 12 times faster on my machine. Where did you pick up that trick?
I need to delve a bit more into it now.
Jason...AKA CirqueDeSQLeil
_______________________________________________
I have given a name to my pain...MCM SQL Server, MVP
SQL RNNR
Posting Performance Based Questions - Gail Shaw[/url]
Learn Extended Events
August 18, 2011 at 9:33 am
SQLRNNR (8/18/2011)
Well, that is about 12 times faster on my machine. Where did you pick up that trick?I need to delve a bit more into it now.
Not really mine, I just converted the oracle query into t-sql.
August 18, 2011 at 9:37 am
Cadavre (8/18/2011)
SQLRNNR (8/18/2011)
Well, that is about 12 times faster on my machine. Where did you pick up that trick?I need to delve a bit more into it now.
Not really mine, I just converted the oracle query into t-sql.
Did you use a tool or something?
Jason...AKA CirqueDeSQLeil
_______________________________________________
I have given a name to my pain...MCM SQL Server, MVP
SQL RNNR
Posting Performance Based Questions - Gail Shaw[/url]
Learn Extended Events
August 18, 2011 at 9:41 am
SQLRNNR (8/18/2011)
Cadavre (8/18/2011)
SQLRNNR (8/18/2011)
Well, that is about 12 times faster on my machine. Where did you pick up that trick?I need to delve a bit more into it now.
Not really mine, I just converted the oracle query into t-sql.
Did you use a tool or something?
Nope, just worked through it. Been a quiet day at work 🙂
August 18, 2011 at 9:43 am
Cadavre (8/18/2011)
SQLRNNR (8/18/2011)
Cadavre (8/18/2011)
SQLRNNR (8/18/2011)
Well, that is about 12 times faster on my machine. Where did you pick up that trick?I need to delve a bit more into it now.
Not really mine, I just converted the oracle query into t-sql.
Did you use a tool or something?
Nope, just worked through it. Been a quiet day at work 🙂
Nice - good job.
I like how you use static values. I think that is where perf is getting killed on mine - hitting back to the dual cte.
Jason...AKA CirqueDeSQLeil
_______________________________________________
I have given a name to my pain...MCM SQL Server, MVP
SQL RNNR
Posting Performance Based Questions - Gail Shaw[/url]
Learn Extended Events
August 18, 2011 at 10:51 am
Well, I found what was causing my solution to run slower. It was relative to that dynamic numbers table but not how I expected.
By removing the selection against the dual table in the anchor of the recursive cte - performance significantly improved. I left it in the remaining places and am seeing similar execution speed as Cadavre.
I have also thrown in a Cross Apply in the final select against dual in order to get a 9 row result set with just 9 values in each row. For that, I also modified the suggestion by bc_. The length parameter was just a bit off in that one, so I changed the last 8 in his suggestion to a 9.
Now, off to get that grid finished for 9col x 9row :w00t:
Jason...AKA CirqueDeSQLeil
_______________________________________________
I have given a name to my pain...MCM SQL Server, MVP
SQL RNNR
Posting Performance Based Questions - Gail Shaw[/url]
Learn Extended Events
August 19, 2011 at 1:56 am
Cool, look forward to the updated blog!
August 23, 2011 at 12:29 am
K - new post will be available @ 6:30am PDT on 8/23
http://jasonbrimhall.info/2011/08/23/tsql-sudoku-ii/
Jason...AKA CirqueDeSQLeil
_______________________________________________
I have given a name to my pain...MCM SQL Server, MVP
SQL RNNR
Posting Performance Based Questions - Gail Shaw[/url]
Learn Extended Events
August 23, 2011 at 7:53 am
SQLRNNR (8/23/2011)
K - new post will be available @ 6:30am PDT on 8/23
Finally able to read it, been waiting all day 😀
I've used your code to add the formatting to mine, PIVOT is not something I'm good with (generally, I'll find a way out of having to use it when I can).
Here's my version: -
DECLARE @SudokuGivens VARCHAR(100)
SET @SudokuGivens = ' 15 6 7 9 4 5 1 9 4 8 3 6 2 7 8 7 35 '
;WITH x( s, ind ) AS (
SELECT @SudokuGivens, Charindex(' ', @SudokuGivens, 1) UNION ALL
SELECT CAST(Substring(s, 1, ind - 1) + CAST(N AS VARCHAR(1)) + Substring(s, ind + 1, 81) AS VARCHAR(100)),
Charindex(' ', s, ind + 1)
FROM x, (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS a(N)
WHERE ind > 0
AND NOT EXISTS (SELECT NULL FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS b(Nn)
WHERE N = Substring(s, ( ( ind - 1 ) / 9 ) * 9 + Nn, 1)
OR N = Substring(s, ( ( ind - 1 ) % 9 ) - 8 + Nn * 9, 1)
OR N = Substring(s, ( ( ( ind - 1 ) / 3 ) % 3 ) * 3 + ( ( ind - 1 ) / 27 ) * 27 + Nn + ( ( Nn - 1 ) / 3 ) * 6 , 1))
)
SELECT rowNumber,[1],[2],[3],[4],[5],[6],[7],[8],[9]
FROM (SELECT S.rowNumber, Row_Number() OVER (Partition BY rowNumber ORDER BY ConcatRow) AS ColNo,
SUBSTRING(ConcatRow, ROW_NUMBER() OVER (Partition BY S.rowNumber ORDER BY ConcatRow), 1) AS DATA
FROM (SELECT ROW_NUMBER() OVER (ORDER BY s) AS rowNumber,
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) 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
I'm going to look into it later if I get chance, with the attempt at some more perf-tuning. A brief comparison on my box shows the above to still be slightly faster than your version, but could do with some more complicated puzzles to test it with.
August 23, 2011 at 8:16 am
Nice. I thought about removing that table variable altogether last night after I posted. I put it in because I was getting weird results. But the weird results got fixed so the table var should not be needed anymore. That should spare me a few ticks.:-D:-D
Jason...AKA CirqueDeSQLeil
_______________________________________________
I have given a name to my pain...MCM SQL Server, MVP
SQL RNNR
Posting Performance Based Questions - Gail Shaw[/url]
Learn Extended Events
August 23, 2011 at 8:25 am
SQLRNNR (8/23/2011)
Nice. I thought about removing that table variable altogether last night after I posted. I put it in because I was getting weird results. But the weird results got fixed so the table var should not be needed anymore. That should spare me a few ticks.:-D:-D
Yep, leaves you about .2 slower on my box at the current point 😛
I've just been hit by an avalanche (metaphorical, not literal 😉 ), so won't be able to perf-tune for awhile. Will hopefully have a look tonight (might even convert it to work with the SQL Challenge)
August 24, 2011 at 3:10 am
Didn't have time for perf-tuning last night, but this morning I quickly knocked up a conversion between the table from the SQL Challenge to a string so the rest of the code doesn't require modifying. Like you, I doubt that a normal user of the script will want to input the Sudoku puzzles into a table so I wanted to leave the functionality for a string input in there.
DECLARE @FromTable INT, --1 means from TC63, else from string
@SudokuGivens VARCHAR(100), @SudokuNo INT
--Intention is to have these values in a proc, with @SudokuGivens and @SudokuNo
--as variable parameters
SET @FromTable = 1
SET @SudokuNo = 1
--SET @SudokuGivens = ' 3 89 3 5422 87 5 2 4 17 1 895 6 63 1 8 4 24 5324 6 18 6 '
IF @SudokuNo IS NULL
BEGIN
SET @SudokuNo = 1 --Default value
END
IF @FromTable = 1
BEGIN
--Put table into string
SELECT @SudokuGivens = COALESCE(@SudokuGivens, '') + Data
FROM (SELECT b.SudokuNo, b.Row, N AS Col, ISNULL(MAX(CONVERT(VARCHAR(MAX),b.Data)),' ') AS Data
FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) a(N)
CROSS APPLY (SELECT SudokuNo, Row, Col, Data
FROM TC63
WHERE a.N = Col AND SudokuNo = @SudokuNo
UNION
SELECT SudokuNo, Row, Col, NULL
FROM TC63
WHERE a.N <> Col AND SudokuNo = @SudokuNo) b
GROUP BY b.SudokuNo, b.Row, N) a
ORDER BY a.Row
END
;WITH Solve(solution, ind ) AS (
SELECT @SudokuGivens, Charindex(' ', @SudokuGivens, 1) UNION ALL
SELECT CAST(Substring(solution, 1, ind - 1) + CAST(N AS VARCHAR(1)) + Substring(solution, ind + 1, 81) AS VARCHAR(100)),
Charindex(' ', solution, ind + 1)
FROM Solve, (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS a(N)
WHERE ind > 0
AND NOT EXISTS (SELECT NULL FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS b(Nn)
WHERE N = Substring(solution, ( ( ind - 1 ) / 9 ) * 9 + Nn, 1)
OR N = Substring(solution, ( ( ind - 1 ) % 9 ) - 8 + Nn * 9, 1)
OR N = Substring(solution, ( ( ( ind - 1 ) / 3 ) % 3 ) * 3 + ( ( ind - 1 ) / 27 ) * 27 + Nn + ( ( Nn - 1 ) / 3 ) * 6 , 1))
)
SELECT @SudokuNo AS SudokuNo, PVT.rowNumber AS [Row/Col],PVT.[1],PVT.[2],PVT.[3],PVT.[4],PVT.[5],PVT.[6],PVT.[7],PVT.[8],PVT.[9]
FROM (SELECT solutionSet.rowNumber, Row_Number() OVER (Partition BY solutionSet.rowNumber ORDER BY solutionSet.workSolution) AS ColNo,
SUBSTRING(solutionSet.workSolution, ROW_NUMBER() OVER (Partition BY solutionSet.rowNumber ORDER BY solutionSet.workSolution), 1) AS DATA
FROM (SELECT ROW_NUMBER() OVER (ORDER BY solution) AS rowNumber,
SUBSTRING(solution, ROW_NUMBER() OVER (ORDER BY solution) * 9 - 8,
ROW_NUMBER() OVER (ORDER BY solution) * 9 - (ROW_NUMBER() OVER (ORDER BY solution) * 9 - 9)) AS workSolution
FROM Solve
CROSS APPLY ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) a(N)
WHERE ind = 0) solutionSet
CROSS APPLY ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) a(N)) prePVT
PIVOT (MAX(prePVT.DATA) FOR ColNo IN ([1],[2],[3],[4],[5],[6],[7],[8],[9])) PVT
August 24, 2011 at 7:40 am
Done some perf-tuning, requires a bit more but ran out of time for today.
On my box
Performed against the following "Givens" -
' 15 6 7 9 4 5 1 9 4 8 3 6 2 7 8 7 35 '
Jason's code[/url] - averaged 2m16s *
Pre-Perf Tuning my code - averaged 1m32s *
Post-Perf Tuning my code - averaged 1m23s *
* average after 10 executions
Version 4 (Perf-Tuned)
DECLARE @FromTable INT, --1 means from TC63, else from string
@SudokuGivens VARCHAR(100), @SudokuNo INT
--Intention is to have these values in a proc, with @SudokuGivens and @SudokuNo
--as variable parameters
--SET @SudokuGivens = 1
--SET @SudokuNo = 1
SET @SudokuGivens = ' 15 6 7 9 4 5 1 9 4 8 3 6 2 7 8 7 35 '
IF @SudokuNo IS NULL
BEGIN
SET @SudokuNo = 1 --Default Value
END
IF @FromTable = 1
BEGIN
SELECT @SudokuGivens = COALESCE(@SudokuGivens, '') + Data
FROM (SELECT b.SudokuNo, b.Row, N AS Col, ISNULL(MAX(CONVERT(VARCHAR(MAX),b.Data)),' ') AS Data
FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) a(N)
CROSS APPLY (SELECT SudokuNo, Row, Col, Data
FROM TC63
WHERE a.N = Col AND SudokuNo = @SudokuNo
UNION
SELECT SudokuNo, Row, Col, NULL
FROM TC63
WHERE a.N <> Col AND SudokuNo = @SudokuNo) b
GROUP BY b.SudokuNo, b.Row, N) a
ORDER BY a.Row
END
;WITH Solve(solution, ind ) AS (
SELECT @SudokuGivens, Charindex(' ', @SudokuGivens, 1) UNION ALL
SELECT CAST(Substring(solution, 1, ind - 1) + CAST(N AS VARCHAR(1)) + Substring(solution, ind + 1, 81) AS VARCHAR(100)),
Charindex(' ', solution, ind + 1)
FROM Solve, (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS a(N)
WHERE ind > 0
AND NOT EXISTS (SELECT NULL FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS b(Nn)
WHERE N = Substring(solution, ( ( ind - 1 ) / 9 ) * 9 + Nn, 1)
OR N = Substring(solution, ( ( ind - 1 ) % 9 ) - 8 + Nn * 9, 1)
OR N = Substring(solution, ( ( ( ind - 1 ) / 3 ) % 3 ) * 3 + ( ( ind - 1 ) / 27 ) * 27 + Nn + ( ( Nn - 1 ) / 3 ) * 6 , 1))
)
SELECT @SudokuNo AS SudokuNo, PVT.rowNumber AS [Row/Col],PVT.[1],PVT.[2],PVT.[3],PVT.[4],PVT.[5],PVT.[6],PVT.[7],PVT.[8],PVT.[9]
FROM (SELECT solutionSet.rowNumber, Row_Number() OVER (Partition BY solutionSet.rowNumber ORDER BY solutionSet.workSolution) AS ColNo,
SUBSTRING(solutionSet.workSolution, ROW_NUMBER() OVER (Partition BY solutionSet.rowNumber ORDER BY solutionSet.workSolution), 1) AS DATA
FROM (SELECT a.N AS rowNumber, SUBSTRING(b.solution, ROW_NUMBER() OVER (ORDER BY b.solution) * 9 - 8,
ROW_NUMBER() OVER (ORDER BY solution) * 9 - (ROW_NUMBER() OVER (ORDER BY solution) * 9 - 9)) AS workSolution
FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS a(N),(SELECT TOP 1 solution FROM Solve WHERE ind = 0) b) solutionSet
CROSS APPLY ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) a(N)) prePVT
PIVOT (MAX(prePVT.DATA) FOR ColNo IN ([1],[2],[3],[4],[5],[6],[7],[8],[9])) PVT
--Edit--
Done some further perf-tuning and have added functionality to attempt to increase the number of "givens" before running the brute force solver. Added this functionality due to the massive amount of time that it took to process a puzzle I found with 17 "givens".
Also fixed a bug where when converting the SudokuGivens from TC63, if there were no values for a particular row/column then that row/column was skipped when printing out the string resulting in a string with less than 81 characters.
Version 5
DECLARE @FromTable INT, --1 means from TC63, else from string
@SudokuGivens VARCHAR(100), @SudokuNo INT
SET @FromTable = 1
SET @SudokuNo = 1
--SET @SudokuGivens = ' 15 6 7 9 4 5 1 9 4 8 3 6 2 7 8 7 35 '
IF @SudokuNo IS NULL
BEGIN
SET @SudokuNo = 1 --Default Value
END
IF @FromTable = 1
BEGIN
;WITH preparePuzzle (row, col, data) AS (
SELECT a.row, a.col, MAX(data) AS data
FROM (SELECT a.n AS row, b.n AS col
FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) a(n)
CROSS APPLY (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) b(n)) a
CROSS APPLY (SELECT sudokuno, row, col,
CASE WHEN a.row = t.row AND a.col = t.col
THEN data
ELSE NULL END AS data
FROM tc63 t
WHERE sudokuno = @SudokuNo) b
GROUP BY a.row, a.col),
attemptIncreaseGivens (data, row, col, pos) AS (
SELECT t5.data, row,col,
( ( t1.row - 1 ) / 3 + 1 ) * 1000 + ( ( t1.col - 1 ) / 3 + 1 ) AS pos
FROM preparePuzzle t1
CROSS JOIN (SELECT data
FROM preparePuzzle
GROUP BY data) t5
WHERE t1.data IS NULL
AND NOT EXISTS (SELECT NULL FROM preparePuzzle t2 WHERE t2.row = t1.row AND t2.data = t5.data)
AND NOT EXISTS (SELECT NULL FROM preparePuzzle t3 WHERE t3.col = t1.col AND t3.data = t5.data)
AND NOT EXISTS (SELECT NULL FROM preparePuzzle t4 WHERE ( ( t4.row - 1 ) / 3 + 1 ) * 1000 + ( ( t4.col - 1 ) / 3 + 1 ) =
( ( t1.row - 1 ) / 3 + 1 ) * 1000 + ( ( t1.col - 1 ) / 3 + 1 ) AND t4.data = t5.data)
GROUP BY t5.data, row, col, ( ( t1.row - 1 ) / 3 + 1 ) * 1000 + ( ( t1.col - 1 ) / 3 + 1 ))
SELECT @SudokuGivens = Coalesce(@SudokuGivens, '') + data
FROM (SELECT row, col, Isnull(CONVERT(CHAR(1), MAX(data)), ' ') AS data
FROM (SELECT a.row, a.col, a.data
FROM (SELECT t1.row, t1.col, t1.data
FROM attemptIncreaseGivens t1
INNER JOIN (SELECT data, pos
FROM attemptIncreaseGivens
GROUP BY data, pos
HAVING COUNT(*) = 1) t2 ON t1.data = t2.data AND t1.pos = t2.pos) a
UNION
SELECT row, col, data
FROM preparePuzzle) a
GROUP BY row, col) b
ORDER BY row,col
END
ELSE
BEGIN
PRINT 'To-Do' --Write similar increaseGivens function for string data
--to help with puzzles that have 17 "givens"
END
;WITH Solve(solution, ind ) AS (
SELECT @SudokuGivens, Charindex(' ', @SudokuGivens, 1) UNION ALL
SELECT CAST(Substring(solution, 1, ind - 1) + CAST(N AS VARCHAR(1)) + Substring(solution, ind + 1, 81) AS VARCHAR(100)),
Charindex(' ', solution, ind + 1)
FROM Solve, (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS a(N)
WHERE ind > 0
AND NOT EXISTS (SELECT NULL FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS b(Nn)
WHERE N = Substring(solution, ( ( ind - 1 ) / 9 ) * 9 + Nn, 1)
OR N = Substring(solution, ( ( ind - 1 ) % 9 ) - 8 + Nn * 9, 1)
OR N = Substring(solution, ( ( ( ind - 1 ) / 3 ) % 3 ) * 3 + ( ( ind - 1 ) / 27 ) * 27 + Nn + ( ( Nn - 1 ) / 3 ) * 6 , 1))
)
SELECT @SudokuNo AS SudokuNo, PVT.rowNumber AS [Row/Col],PVT.[1],PVT.[2],PVT.[3],PVT.[4],PVT.[5],PVT.[6],PVT.[7],PVT.[8],PVT.[9]
FROM (SELECT solutionSet.rowNumber, ROW_NUMBER() OVER (Partition BY solutionSet.rowNumber ORDER BY solutionSet.workSolution) AS ColNo,
Substring(solutionSet.workSolution, ROW_NUMBER() OVER (Partition BY solutionSet.rowNumber ORDER BY solutionSet.workSolution), 1) AS DATA
FROM (SELECT a.N AS rowNumber, Substring(b.solution, ROW_NUMBER() OVER (ORDER BY b.solution) * 9 - 8,
ROW_NUMBER() OVER (ORDER BY solution) * 9 - (ROW_NUMBER() OVER (ORDER BY solution) * 9 - 9)) AS workSolution
FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS a(N),(SELECT TOP 1 solution FROM Solve WHERE ind = 0) b) solutionSet
CROSS APPLY ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) a(N)) prePVT
PIVOT (MAX(prePVT.DATA) FOR ColNo IN ([1],[2],[3],[4],[5],[6],[7],[8],[9])) PVT
Still need to add the same functionality for when the user is entering a string, but I'm off to Reading festival tonight so won't be in any state to look at it again until at least Tuesday 😛
--Edit 2--
OK, added the same functionality to increase the number of "givens" for a string.
DECLARE @FromTable INT, --1 means from TC63, else from string
@SudokuGivens VARCHAR(100), @SudokuNo INT
--Able to be set as parameters in a sproc instead
SET @FromTable = 1
SET @SudokuNo = 1
--SET @SudokuGivens = ' 3 89 3 5422 87 5 2 4 17 1 895 6 63 1 8 4 24 5324 6 18 6 '
IF @SudokuNo IS NULL
BEGIN
SET @SudokuNo = 1 --Default Value
END
IF @FromTable = 1
BEGIN
IF @SudokuGivens IS NOT NULL
BEGIN
SET @SudokuGivens = NULL
END
;WITH preparePuzzle (row, col, data) AS (
SELECT a.row, a.col, MAX(data) AS data
FROM (SELECT a.n AS row, b.n AS col
FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) a(n)
CROSS APPLY (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) b(n)) a
CROSS APPLY (SELECT sudokuno, row, col,
CASE WHEN a.row = t.row AND a.col = t.col
THEN data
ELSE NULL END AS data
FROM tc63 t
WHERE sudokuno = @SudokuNo) b
GROUP BY a.row, a.col),
attemptIncreaseGivens (data, row, col, pos) AS (
SELECT t5.data, row,col,
( ( t1.row - 1 ) / 3 + 1 ) * 1000 + ( ( t1.col - 1 ) / 3 + 1 ) AS pos
FROM preparePuzzle t1
CROSS JOIN (SELECT data
FROM preparePuzzle
GROUP BY data) t5
WHERE t1.data IS NULL
AND NOT EXISTS (SELECT NULL FROM preparePuzzle t2 WHERE t2.row = t1.row AND t2.data = t5.data)
AND NOT EXISTS (SELECT NULL FROM preparePuzzle t3 WHERE t3.col = t1.col AND t3.data = t5.data)
AND NOT EXISTS (SELECT NULL FROM preparePuzzle t4 WHERE ( ( t4.row - 1 ) / 3 + 1 ) * 1000 + ( ( t4.col - 1 ) / 3 + 1 ) =
( ( t1.row - 1 ) / 3 + 1 ) * 1000 + ( ( t1.col - 1 ) / 3 + 1 ) AND t4.data = t5.data)
GROUP BY t5.data, row, col, ( ( t1.row - 1 ) / 3 + 1 ) * 1000 + ( ( t1.col - 1 ) / 3 + 1 ))
SELECT @SudokuGivens = Coalesce(@SudokuGivens, '') + data
FROM (SELECT row, col, Isnull(CONVERT(CHAR(1), MAX(data)), ' ') AS data
FROM (SELECT a.row, a.col, a.data
FROM (SELECT t1.row, t1.col, t1.data
FROM attemptIncreaseGivens t1
INNER JOIN (SELECT data, pos
FROM attemptIncreaseGivens
GROUP BY data, pos
HAVING COUNT(*) = 1) t2 ON t1.data = t2.data AND t1.pos = t2.pos) a
UNION
SELECT row, col, data
FROM preparePuzzle) a
GROUP BY row, col) b
ORDER BY row,col
END
ELSE
BEGIN
DECLARE @TempSudokuGivens VARCHAR(100) = @SudokuGivens
SET @SudokuGivens = NULL
;WITH preparePuzzle (row, col, data) AS (
SELECT puzzleSet.rowNumber AS row, ROW_NUMBER() OVER (Partition BY puzzleSet.rowNumber ORDER BY puzzleSet.workPuzzle) AS col,
NULLIF(Substring(puzzleSet.workPuzzle, ROW_NUMBER() OVER (Partition BY puzzleSet.rowNumber ORDER BY puzzleSet.workPuzzle), 1),'') AS data
FROM (SELECT a.N AS rowNumber, Substring(b.puzzle, ROW_NUMBER() OVER (ORDER BY b.puzzle) * 9 - 8,
ROW_NUMBER() OVER (ORDER BY puzzle) * 9 - (ROW_NUMBER() OVER (ORDER BY puzzle) * 9 - 9)) AS workPuzzle
FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS a(N),(SELECT @TempSudokuGivens AS puzzle) b) puzzleSet
CROSS APPLY ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) a(N)),
attemptIncreaseGivens (data, row, col, pos) AS (
SELECT t5.data, row,col,
( ( t1.row - 1 ) / 3 + 1 ) * 1000 + ( ( t1.col - 1 ) / 3 + 1 ) AS pos
FROM preparePuzzle t1
CROSS JOIN (SELECT data
FROM preparePuzzle
GROUP BY data) t5
WHERE t1.data IS NULL
AND NOT EXISTS (SELECT NULL FROM preparePuzzle t2 WHERE t2.row = t1.row AND t2.data = t5.data)
AND NOT EXISTS (SELECT NULL FROM preparePuzzle t3 WHERE t3.col = t1.col AND t3.data = t5.data)
AND NOT EXISTS (SELECT NULL FROM preparePuzzle t4 WHERE ( ( t4.row - 1 ) / 3 + 1 ) * 1000 + ( ( t4.col - 1 ) / 3 + 1 ) =
( ( t1.row - 1 ) / 3 + 1 ) * 1000 + ( ( t1.col - 1 ) / 3 + 1 ) AND t4.data = t5.data)
GROUP BY t5.data, row, col, ( ( t1.row - 1 ) / 3 + 1 ) * 1000 + ( ( t1.col - 1 ) / 3 + 1 ))
SELECT @SudokuGivens = Coalesce(@SudokuGivens, '') + data
FROM (SELECT row, col, Isnull(CONVERT(CHAR(1), MAX(data)), ' ') AS data
FROM (SELECT a.row, a.col, a.data
FROM (SELECT t1.row, t1.col, t1.data
FROM attemptIncreaseGivens t1
INNER JOIN (SELECT data, pos
FROM attemptIncreaseGivens
GROUP BY data, pos
HAVING COUNT(*) = 1) t2 ON t1.data = t2.data AND t1.pos = t2.pos) a
UNION
SELECT row, col, data
FROM preparePuzzle) a
GROUP BY row, col) b
ORDER BY row,col
END
;WITH Solve(solution, ind ) AS (
SELECT @SudokuGivens, Charindex(' ', @SudokuGivens, 1) UNION ALL
SELECT CAST(Substring(solution, 1, ind - 1) + CAST(N AS VARCHAR(1)) + Substring(solution, ind + 1, 81) AS VARCHAR(100)),
Charindex(' ', solution, ind + 1)
FROM Solve, (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS a(N)
WHERE ind > 0
AND NOT EXISTS (SELECT NULL FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS b(Nn)
WHERE N = Substring(solution, ( ( ind - 1 ) / 9 ) * 9 + Nn, 1)
OR N = Substring(solution, ( ( ind - 1 ) % 9 ) - 8 + Nn * 9, 1)
OR N = Substring(solution, ( ( ( ind - 1 ) / 3 ) % 3 ) * 3 + ( ( ind - 1 ) / 27 ) * 27 + Nn + ( ( Nn - 1 ) / 3 ) * 6 , 1)))
SELECT solutionSet.rowNumber, ROW_NUMBER() OVER (Partition BY solutionSet.rowNumber ORDER BY solutionSet.workSolution) AS ColNo,
Substring(solutionSet.workSolution, ROW_NUMBER() OVER (Partition BY solutionSet.rowNumber ORDER BY solutionSet.workSolution), 1) AS DATA
FROM (SELECT a.N AS rowNumber, Substring(b.solution, ROW_NUMBER() OVER (ORDER BY b.solution) * 9 - 8,
ROW_NUMBER() OVER (ORDER BY solution) * 9 - (ROW_NUMBER() OVER (ORDER BY solution) * 9 - 9)) AS workSolution
FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS a(N),(SELECT TOP 1 solution FROM Solve WHERE ind = 0) b) solutionSet
CROSS APPLY ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) a(N)
Considering whether or not it's worth adding in any other methods to increase the number of "givens" before we brute force the result. For now, I think this'll do. 🙂
Removed the holding variables in favour of a cascading CTE approach. Still considering whether or not it's worth adding further methods to increase the number givens before we brute force the result. Version 7 is not really a great deal better than Version 6, worked out at about a 0.5% difference on my machine, but I wanted to make it a pure CTE solution 🙂
Version 7
DECLARE @FromTable INT, --1 means from TC63, else from string
@SudokuGivens VARCHAR(100), @SudokuNo INT
--Able to be set as parameters in a sproc instead
SET @FromTable = 1
SET @SudokuNo = 1
--SET @SudokuGivens = ' 3 89 3 5422 87 5 2 4 17 1 895 6 63 1 8 4 24 5324 6 18 6 '
IF @SudokuNo IS NULL
BEGIN
SET @SudokuNo = 1 --Default Value
END
IF @FromTable = 1
BEGIN
;WITH preparePuzzle (row, col, data) AS (
SELECT a.row, a.col, MAX(data) AS data
FROM (SELECT a.n AS row, b.n AS col
FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) a(n)
CROSS APPLY (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) b(n)) a
CROSS APPLY (SELECT sudokuno, row, col,
CASE WHEN a.row = t.row AND a.col = t.col
THEN data
ELSE NULL END AS data
FROM tc63 t
WHERE sudokuno = @SudokuNo) b
GROUP BY a.row, a.col),
attemptIncreaseGivens (data, row, col, pos) AS (
SELECT t5.data, row,col,
( ( t1.row - 1 ) / 3 + 1 ) * 1000 + ( ( t1.col - 1 ) / 3 + 1 ) AS pos
FROM preparePuzzle t1
CROSS JOIN (SELECT data
FROM preparePuzzle
GROUP BY data) t5
WHERE t1.data IS NULL
AND NOT EXISTS (SELECT NULL FROM preparePuzzle t2 WHERE t2.row = t1.row AND t2.data = t5.data)
AND NOT EXISTS (SELECT NULL FROM preparePuzzle t3 WHERE t3.col = t1.col AND t3.data = t5.data)
AND NOT EXISTS (SELECT NULL FROM preparePuzzle t4 WHERE ( ( t4.row - 1 ) / 3 + 1 ) * 1000 + ( ( t4.col - 1 ) / 3 + 1 ) =
( ( t1.row - 1 ) / 3 + 1 ) * 1000 + ( ( t1.col - 1 ) / 3 + 1 ) AND t4.data = t5.data)
GROUP BY t5.data, row, col, ( ( t1.row - 1 ) / 3 + 1 ) * 1000 + ( ( t1.col - 1 ) / 3 + 1 )),
prepareGivens (sudokuGivens) AS (
SELECT CONVERT(VARCHAR(100),REPLACE(data,' ',' ')) AS data
FROM (SELECT ISNULL(data, ' ')
FROM (SELECT row, col, CONVERT(CHAR(1), MAX(data)) AS data
FROM (SELECT a.row, a.col, a.data
FROM (SELECT t1.row, t1.col, t1.data
FROM attemptIncreaseGivens t1
INNER JOIN (SELECT data, pos
FROM attemptIncreaseGivens
GROUP BY data, pos
HAVING COUNT(*) = 1) t2 ON t1.data = t2.data AND t1.pos = t2.pos) a
UNION
SELECT row, col, data
FROM preparePuzzle) a
GROUP BY row, col) b
ORDER BY row,col
FOR XML PATH('')) a(data)),
Solve(solution, ind ) AS (
SELECT sudokuGivens, Charindex(' ', sudokuGivens, 1)
FROM prepareGivens UNION ALL
SELECT CAST(Substring(solution, 1, ind - 1) + CAST(N AS VARCHAR(1)) + Substring(solution, ind + 1, 81) AS VARCHAR(100)),
Charindex(' ', solution, ind + 1)
FROM Solve, (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS a(N)
WHERE ind > 0
AND NOT EXISTS (SELECT NULL FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS b(Nn)
WHERE N = Substring(solution, ( ( ind - 1 ) / 9 ) * 9 + Nn, 1)
OR N = Substring(solution, ( ( ind - 1 ) % 9 ) - 8 + Nn * 9, 1)
OR N = Substring(solution, ( ( ( ind - 1 ) / 3 ) % 3 ) * 3 + ( ( ind - 1 ) / 27 ) * 27 + Nn + ( ( Nn - 1 ) / 3 ) * 6 , 1)))
SELECT ISNULL(@SudokuNo,1) AS SudokuNo, PVT.rowNumber AS [Row/Col],PVT.[1],PVT.[2],PVT.[3],PVT.[4],PVT.[5],PVT.[6],PVT.[7],PVT.[8],PVT.[9]
FROM (SELECT solutionSet.rowNumber, ROW_NUMBER() OVER (Partition BY solutionSet.rowNumber ORDER BY solutionSet.workSolution) AS ColNo,
Substring(solutionSet.workSolution, ROW_NUMBER() OVER (Partition BY solutionSet.rowNumber ORDER BY solutionSet.workSolution), 1) AS DATA
FROM (SELECT a.N AS rowNumber, Substring(b.solution, ROW_NUMBER() OVER (ORDER BY b.solution) * 9 - 8,
ROW_NUMBER() OVER (ORDER BY solution) * 9 - (ROW_NUMBER() OVER (ORDER BY solution) * 9 - 9)) AS workSolution
FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS a(N),(SELECT TOP 1 solution FROM Solve WHERE ind = 0) b) solutionSet
CROSS APPLY ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) a(N)) prePVT
PIVOT (MAX(prePVT.DATA) FOR ColNo IN ([1],[2],[3],[4],[5],[6],[7],[8],[9])) PVT
END
ELSE
BEGIN
;WITH preparePuzzle (row, col, data) AS (
SELECT puzzleSet.rowNumber AS row, ROW_NUMBER() OVER (Partition BY puzzleSet.rowNumber ORDER BY puzzleSet.workPuzzle) AS col,
NULLIF(Substring(puzzleSet.workPuzzle, ROW_NUMBER() OVER (Partition BY puzzleSet.rowNumber ORDER BY puzzleSet.workPuzzle), 1),'') AS data
FROM (SELECT a.N AS rowNumber, Substring(b.puzzle, ROW_NUMBER() OVER (ORDER BY b.puzzle) * 9 - 8,
ROW_NUMBER() OVER (ORDER BY puzzle) * 9 - (ROW_NUMBER() OVER (ORDER BY puzzle) * 9 - 9)) AS workPuzzle
FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS a(N),(SELECT @SudokuGivens AS puzzle) b) puzzleSet
CROSS APPLY ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) a(N)),
attemptIncreaseGivens (data, row, col, pos) AS (
SELECT t5.data, row,col,
( ( t1.row - 1 ) / 3 + 1 ) * 1000 + ( ( t1.col - 1 ) / 3 + 1 ) AS pos
FROM preparePuzzle t1
CROSS JOIN (SELECT data
FROM preparePuzzle
GROUP BY data) t5
WHERE t1.data IS NULL
AND NOT EXISTS (SELECT NULL FROM preparePuzzle t2 WHERE t2.row = t1.row AND t2.data = t5.data)
AND NOT EXISTS (SELECT NULL FROM preparePuzzle t3 WHERE t3.col = t1.col AND t3.data = t5.data)
AND NOT EXISTS (SELECT NULL FROM preparePuzzle t4 WHERE ( ( t4.row - 1 ) / 3 + 1 ) * 1000 + ( ( t4.col - 1 ) / 3 + 1 ) =
( ( t1.row - 1 ) / 3 + 1 ) * 1000 + ( ( t1.col - 1 ) / 3 + 1 ) AND t4.data = t5.data)
GROUP BY t5.data, row, col, ( ( t1.row - 1 ) / 3 + 1 ) * 1000 + ( ( t1.col - 1 ) / 3 + 1 )),
prepareGivens (sudokuGivens) AS (
SELECT CONVERT(VARCHAR(100),REPLACE(data,' ',' ')) AS data
FROM (SELECT ISNULL(data, ' ')
FROM (SELECT row, col, CONVERT(CHAR(1), MAX(data)) AS data
FROM (SELECT a.row, a.col, a.data
FROM (SELECT t1.row, t1.col, t1.data
FROM attemptIncreaseGivens t1
INNER JOIN (SELECT data, pos
FROM attemptIncreaseGivens
GROUP BY data, pos
HAVING COUNT(*) = 1) t2 ON t1.data = t2.data AND t1.pos = t2.pos) a
UNION
SELECT row, col, data
FROM preparePuzzle) a
GROUP BY row, col) b
ORDER BY row,col
FOR XML PATH('')) a(data)),
Solve(solution, ind ) AS (
SELECT sudokuGivens, Charindex(' ', sudokuGivens, 1)
FROM prepareGivens UNION ALL
SELECT CAST(Substring(solution, 1, ind - 1) + CAST(N AS VARCHAR(1)) + Substring(solution, ind + 1, 81) AS VARCHAR(100)),
Charindex(' ', solution, ind + 1)
FROM Solve, (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS a(N)
WHERE ind > 0
AND NOT EXISTS (SELECT NULL FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS b(Nn)
WHERE N = Substring(solution, ( ( ind - 1 ) / 9 ) * 9 + Nn, 1)
OR N = Substring(solution, ( ( ind - 1 ) % 9 ) - 8 + Nn * 9, 1)
OR N = Substring(solution, ( ( ( ind - 1 ) / 3 ) % 3 ) * 3 + ( ( ind - 1 ) / 27 ) * 27 + Nn + ( ( Nn - 1 ) / 3 ) * 6 , 1)))
SELECT ISNULL(@SudokuNo,1) AS SudokuNo, PVT.rowNumber AS [Row/Col],PVT.[1],PVT.[2],PVT.[3],PVT.[4],PVT.[5],PVT.[6],PVT.[7],PVT.[8],PVT.[9]
FROM (SELECT solutionSet.rowNumber, ROW_NUMBER() OVER (Partition BY solutionSet.rowNumber ORDER BY solutionSet.workSolution) AS ColNo,
Substring(solutionSet.workSolution, ROW_NUMBER() OVER (Partition BY solutionSet.rowNumber ORDER BY solutionSet.workSolution), 1) AS DATA
FROM (SELECT a.N AS rowNumber, Substring(b.solution, ROW_NUMBER() OVER (ORDER BY b.solution) * 9 - 8,
ROW_NUMBER() OVER (ORDER BY solution) * 9 - (ROW_NUMBER() OVER (ORDER BY solution) * 9 - 9)) AS workSolution
FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) AS a(N),(SELECT TOP 1 solution FROM Solve WHERE ind = 0) b) solutionSet
CROSS APPLY ( VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) a(N)) prePVT
PIVOT (MAX(prePVT.DATA) FOR ColNo IN ([1],[2],[3],[4],[5],[6],[7],[8],[9])) PVT
END
Viewing 13 posts - 16 through 27 (of 27 total)
You must be logged in to reply to this topic. Login to reply