Post date: Aug 19, 2018 1:50:2 PM
"Write a brute force sudoku solver."
Now this is wrong. Very wrong. A SQL sudoku-solver. Something that absolutely should never be written in SQL.
I really didn't want to do this. I had to learn how to solve sudoku, for one, and that took Google, because I know zilch about sudoku (and am pretty uninterested in it). An article by Peter Norvig was very helpful.
CREATE PROCEDURE dbo.suInitializeTables
@grid varchar(81)
AS
BEGIN
DECLARE @current char(1), @r int = 1, @c int = 1
WHILE @grid <> ''
BEGIN
SET @current = LEFT(@grid, 1)
SET @grid = STUFF(@grid, 1, 1, '')
INSERT INTO #Cells (r, c, b, v)
SELECT @r, @c
, CASE
WHEN @r BETWEEN 1 AND 3 AND @c BETWEEN 1 AND 3 THEN 1
WHEN @r BETWEEN 1 AND 3 AND @c BETWEEN 4 AND 6 THEN 2
WHEN @r BETWEEN 1 AND 3 AND @c BETWEEN 7 AND 9 THEN 3
WHEN @r BETWEEN 4 AND 6 AND @c BETWEEN 1 AND 3 THEN 4
WHEN @r BETWEEN 4 AND 6 AND @c BETWEEN 4 AND 6 THEN 5
WHEN @r BETWEEN 4 AND 6 AND @c BETWEEN 7 AND 9 THEN 6
WHEN @r BETWEEN 7 AND 9 AND @c BETWEEN 1 AND 3 THEN 7
WHEN @r BETWEEN 7 AND 9 AND @c BETWEEN 4 AND 6 THEN 8
WHEN @r BETWEEN 7 AND 9 AND @c BETWEEN 7 AND 9 THEN 9
END AS b
, CASE WHEN @current = '0' THEN NULL ELSE @current END AS v
-- Move around the grid
IF @c = 9
SELECT @c = 1, @r = @r + 1
ELSE
SELECT @c = @c + 1
END
-- Fill in available values. Don't write anything for cells that have a set value
; WITH Nine (q) AS
(
SELECT 1
UNION ALL
SELECT q + 1
FROM Nine
WHERE q < 9
)
INSERT INTO #Available (r, c, v, b)
SELECT c.r, c.c, n.q
, CASE
WHEN c.r BETWEEN 1 AND 3 AND c.c BETWEEN 1 AND 3 THEN 1
WHEN c.r BETWEEN 1 AND 3 AND c.c BETWEEN 4 AND 6 THEN 2
WHEN c.r BETWEEN 1 AND 3 AND c.c BETWEEN 7 AND 9 THEN 3
WHEN c.r BETWEEN 4 AND 6 AND c.c BETWEEN 1 AND 3 THEN 4
WHEN c.r BETWEEN 4 AND 6 AND c.c BETWEEN 4 AND 6 THEN 5
WHEN c.r BETWEEN 4 AND 6 AND c.c BETWEEN 7 AND 9 THEN 6
WHEN c.r BETWEEN 7 AND 9 AND c.c BETWEEN 1 AND 3 THEN 7
WHEN c.r BETWEEN 7 AND 9 AND c.c BETWEEN 4 AND 6 THEN 8
WHEN c.r BETWEEN 7 AND 9 AND c.c BETWEEN 7 AND 9 THEN 9
END
FROM Nine n
CROSS JOIN #Cells c
WHERE c.v iS NULL
END
GO
CREATE PROCEDURE dbo.suKillPeers
AS
BEGIN
-- Clear out the available values for the populated cells (not technically peers, just an artifact of this DB)
DELETE a
FROM #Cells c
INNER JOIN #Available a
ON a.r = c.r
AND a.c = c.c
WHERE c.v IS NOT NULL
-- Eliminate row peers
DELETE a
FROM #Cells c
INNER JOIN #Available a
ON a.r = c.r
AND a.v = c.v
WHERE c.v IS NOT NULL
-- Eliminate column peers
DELETE a
FROM #Cells c
INNER JOIN #Available a
ON a.c = c.c
AND a.v = c.v
WHERE c.v IS NOT NULL
-- Eliminate box peers
DELETE a
FROM #Cells c
INNER JOIN #Available a
ON a.b = c.b
AND a.v = c.v
WHERE c.v IS NOT NULL
END
GO
CREATE PROCEDURE dbo.suConstraintPropagation
AS
BEGIN
DECLARE @DidWork bit = 0
WHILE 1 = 1 BEGIN
SET @DidWork = 0
-- There is only a single digit choice for a square
; WITH OnlyOne (r, c, v) AS
(
SELECT c.r, c.c, MIN(c.v)
FROM #Available c
GROUP BY c.r, c.c
HAVING COUNT(*) = 1
)
UPDATE c
SET c.v = o.v
FROM #Cells c
INNER JOIN OnlyOne o
ON o.c = c.c
AND o.r = c.r
IF @@ROWCOUNT > 0
SET @DidWork = 1
EXEC suKillPeers
-- There is only one square choice for a digit in a row
; WITH OnlyOne (r, c, v) AS
(
SELECT c.r, MIN(c.c), c.v
FROM #Available c
GROUP BY c.r, c.v
HAVING COUNT(*) = 1
)
UPDATE c
SET c.v = o.v
FROM #Cells c
INNER JOIN OnlyOne o
ON o.c = c.c
AND o.r = c.r
IF @@ROWCOUNT > 0
SET @DidWork = 1
EXEC suKillPeers
-- There is only one square choice for a digit in a column
; WITH OnlyOne (r, c, v) AS
(
SELECT MIN(c.r), c.c, c.v
FROM #Available c
GROUP BY c.c, c.v
HAVING COUNT(*) = 1
)
UPDATE c
SET c.v = o.v
FROM #Cells c
INNER JOIN OnlyOne o
ON o.c = c.c
AND o.r = c.r
IF @@ROWCOUNT > 0
SET @DidWork = 1
EXEC suKillPeers
-- There is only one square choice for a digit in a box
; WITH OnlyOne (r, c, v) AS
(
SELECT MIN(c.r), MIN(c.c), c.v
FROM #Available c
GROUP BY c.b, c.v
HAVING COUNT(*) = 1
)
UPDATE c
SET c.v = o.v
FROM #Cells c
INNER JOIN OnlyOne o
ON o.c = c.c
AND o.r = c.r
IF @@ROWCOUNT > 0
SET @DidWork = 1
EXEC suKillPeers
-- Exit if we are no longer doing any work
IF @DidWork = 0 BREAK
END -- While
END
GO
CREATE PROCEDURE dbo.suTrialAndError
AS
BEGIN
DECLARE @c TINYINT, @r TINYINT, @v TINYINT, @a INT = 0
WHILE 1 = 1
BEGIN
; WITH Options1 AS
(
SELECT r, c, v
, COUNT(*) OVER (PARTITION BY r, c) AS cnt
FROM #Available
),
Options2 AS
(
SELECT *, ROW_NUMBER() OVER (ORDER BY cnt, r, c, v) AS a
FROM Options1
)
SELECT TOP (1) @c = c, @r = r, @v = v, @a = a
FROM Options2
WHERE a > @a
-- IF we finished with all our possible attempts, exit
IF @@ROWCOUNT = 0 RETURN
BEGIN TRY
BEGIN TRANSACTION
UPDATE #Cells
SET v = @v
WHERE c = @c
AND r = @r
EXEC suKillPeers
EXEC suConstraintPropagation
IF EXISTS (SELECT 1
FROM #Cells c
LEFT OUTER JOIN #Available a
ON a.r = c.r
AND a.c = c.c
WHERE c.v IS NULL
AND a.r IS NULL)
RAISERROR('Incorrect choice', 16, 1)
COMMIT TRANSACTION
-- We changed the source data, so we have to start over at the list start
SET @a = 0
IF NOT EXISTS (SELECT 1 FROM #Available)
RETURN -- Solved
END TRY
BEGIN CATCH
IF @@TRANCOUNT> 0 ROLLBACK TRANSACTION
END CATCH
END -- While
END
GO
CREATE TABLE #Cells
(
r TINYINT NOT NULL
, c TINYINT NOT NULL
, b TINYINT NOT NULL
, v TINYINT NULL
, PRIMARY KEY (r, c)
)
CREATE TABLE #Available
(
r TINYINT NOT NULL
, c TINYINT NOT NULL
, v TINYINT NOT NULL
, b TINYINT NOT NULL
, PRIMARY KEY (r, c, v)
)
CREATE TABLE #Sudo (getMeASandwich varchar(50))
BULK INSERT #Sudo FROM 'E:\sudoku.txt' WITH (ROWTERMINATOR = '0x0a')
ALTER TABLE #Sudo ADD id INT NOT NULL IDENTITY(1,1)
-- Delete the lines that say GRID SOMETHING
DELETE FROM #Sudo
WHERE id % 10 = 1
DECLARE @Sudoku varchar(81), @answer int = 0
WHILE 1 = 1
BEGIN
-- Build a nice string of 81 digits, suitable for easily passing into a SP w/o extra work
SET @Sudoku = ''
WHILE LEN(@Sudoku) < 81
BEGIN
SELECT TOP (1) @Sudoku = @Sudoku + getMeASandwich
FROM #Sudo
ORDER BY id
; WITH DeleteMe AS (SELECT TOP (1) * FROM #Sudo ORDER BY id)
DELETE FROM DeleteMe
END -- Looping through 9 rows
-- Solve the puzzle
EXEC suInitializeTables @Sudoku
EXEC suConstraintPropagation
EXEC suTrialAndError
SELECT @answer = @answer +
SUM(CASE c
WHEN 1 THEN 100
WHEN 2 THEN 10
WHEN 3 THEN 1
END * v)
FROM #Cells
WHERE r = 1
AND c IN (1, 2, 3)
-- Exit when we have processed everything
IF NOT EXISTS (SELECT 1 FROM #Sudo)
BREAK
TRUNCATE TABLE #Cells
TRUNCATE TABLE #Available
END
SELECT @answer
DROP TABLE #Sudo
DROP TABLE #Cells
DROP TABLE #Available
GO
DROP PROCEDURE dbo.suInitializeTables
GO
DROP PROCEDURE dbo.suConstraintPropagation
GO
DROP PROCEDURE dbo.suKillPeers
GO
DROP PROCEDURE dbo.suTrialAndError
GO