Use TSQL to play Sudoku

After the “Balda” was successfully solved with the help of TSQL (article) I decided to try to solve “Sudoku” on it (thanks for the idea of shavluk ).

Sudoku's solution was surprisingly simple.

The basic scheme is as follows:

Description of tables:

SudokuCell - description of the properties (region, row, column) of all cells;
SudokuValue - valid cell values;
SudokuField is a field for specifying known digits.

Script for creating tables:

--       IF EXISTS (SELECT * FROM sysobjects WHERE name='SudokuField') DROP TABLE SudokuField; IF EXISTS (SELECT * FROM sysobjects WHERE name='SudokuCell') DROP TABLE SudokuCell; IF EXISTS (SELECT * FROM sysobjects WHERE name='SudokuValue') DROP TABLE SudokuValue; ---------------------------------------------- --      ---------------------------------------------- CREATE TABLE SudokuCell( ID int NOT NULL, -- ID  RegionID int NOT NULL, --  RowID int NOT NULL, --  ColID int NOT NULL, --  CONSTRAINT PK_SudokuCell PRIMARY KEY(ID) ) GO --   INSERT SudokuCell(ID,RegionID,RowID,ColID) SELECT reg.ID*100+ri*10+cj, reg.ID, (reg.ID/10-1)*3+ri, (reg.ID-1)%10*3+cj FROM (VALUES (11),(12),(13),(21),(22),(23),(31),(32),(33)) reg(ID) CROSS JOIN (VALUES(1),(2),(3)) r(i) CROSS JOIN (VALUES(1),(2),(3)) c(j) GO ---------------------------------------------- --  1-9 ( ) ---------------------------------------------- CREATE TABLE SudokuValue( Value char(1) NOT NULL, CONSTRAINT PK_SudokuValue PRIMARY KEY(Value) ) GO --   INSERT SudokuValue(Value) VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9) GO ---------------------------------------------- --  ---------------------------------------------- CREATE TABLE SudokuField( CellID int NOT NULL, Value char(1) NOT NULL, CONSTRAINT PK_SudokuField PRIMARY KEY(CellID), CONSTRAINT FK_SudokuField_CellID FOREIGN KEY(CellID) REFERENCES SudokuCell(ID), CONSTRAINT FK_SudokuField_Value FOREIGN KEY(Value) REFERENCES SudokuValue(Value) ) GO

')
We fill the field with known figures as follows:

 --   ,       TRUNCATE TABLE SudokuField GO --     INSERT SudokuField(CellID,Value)VALUES (1122,'3'),(1123,'4'), (1211,'1'),(1212,'5'), (1322,'8'),(1323,'9'),(1333,'3'), (2112,'2'),(2122,'4'),(2123,'7'),(2133,'9'), (2212,'6'),(2223,'9'),(2232,'2'), (2311,'8'),(2333,'1'), (3111,'1'), (3213,'2'),(3221,'9'), (3313,'5'),(3332,'7'),(3333,'4') GO

The cell identifier (CellID) is constructed as follows:

The first and second digits of the number indicate what region it is (row, column);
The third and fourth digit is the row and column number in the region.

Initial options for filling I took from the following site - link .

Let's see what the field looks like:

 --     SELECT ISNULL([1],'') [1], ISNULL([2],'') [2], ISNULL([3],'') [3], ISNULL([4],'') [4], ISNULL([5],'') [5], ISNULL([6],'') [6], ISNULL([7],'') [7], ISNULL([8],'') [8], ISNULL([9],'') [9] FROM ( SELECT c.RowID,c.ColID,f.Value FROM SudokuCell c LEFT JOIN SudokuField f ON f.CellID=c.ID ) q PIVOT(MAX(Value) FOR ColID IN([1],[2],[3],[4],[5],[6],[7],[8],[9])) p ORDER BY RowID

Then comes the solution search algorithm with comments:

 --     DECLARE @StartTime datetime=SYSDATETIME(); --       SELECT --    -       RIGHT(CONCAT('0',CAST(CellNo AS varchar(2)),CHAR(ASCII('a')+Value-1)),3) ID, * INTO #SudokuVariant FROM ( --     SELECT ID CellID,RowID,ColID,RegionID, --   CAST(DENSE_RANK()OVER(ORDER BY ID) AS int) CellNo FROM SudokuCell WHERE ID NOT IN(SELECT CellID FROM SudokuField) ) e CROSS APPLY ( --   ,         SELECT v.Value FROM SudokuCell c JOIN SudokuField f ON f.CellID=c.ID AND (c.ColID=e.ColID OR c.RowID=e.RowID OR c.RegionID=e.RegionID) RIGHT JOIN SudokuValue v ON v.Value=f.Value WHERE c.ID IS NULL --   ,    // ) v --SELECT * FROM #SudokuVariant --       CREATE TABLE #SudokuTree( CellNo int NOT NULL, VariantPath varchar(1000) NOT NULL ) --       CellNo=1 INSERT #SudokuTree(CellNo,VariantPath) SELECT CellNo,ID FROM #SudokuVariant WHERE CellNo=1 --SELECT * FROM #SudokuTree --     DECLARE @MaxCellNo int=(SELECT MAX(CellNo) FROM #SudokuVariant) --      DECLARE @CurrCellNo int=1 DECLARE @NextCellNo int=@CurrCellNo+1 --   WHILE @CurrCellNo<@MaxCellNo BEGIN --   INSERT #SudokuTree(CellNo,VariantPath) SELECT v.CellNo, CONCAT(t.VariantPath,v.ID) FROM #SudokuTree t JOIN #SudokuVariant v ON t.CellNo=@CurrCellNo AND v.CellNo=@NextCellNo /*        ,    //      , ..         #SudokuVariant */ WHERE NOT EXISTS( SELECT * FROM #SudokuVariant i WHERE i.CellNo<@NextCellNo --     --AND t.VariantPath LIKE '%'+i.ID+'%' AND CHARINDEX(i.ID,t.VariantPath)>0 --      -  AND (i.RegionID=v.RegionID OR i.RowID=v.RowID OR i.ColID=v.ColID) AND i.Value=v.Value ) /* ..       VariantPath,         , -        */ --DELETE #SudokuTree WHERE CellNo=@CurrCellNo --     SET @CurrCellNo+=1 SET @NextCellNo+=1 END --SELECT * FROM #SudokuTree WHERE CellNo=@MaxCellNo --     INSERT SudokuField(CellID,Value) SELECT v.CellID,v.Value FROM #SudokuVariant v JOIN ( --    ,    SELECT TOP 1 * FROM #SudokuTree WHERE CellNo=@MaxCellNo --      ) r ON r.VariantPath LIKE '%'+v.ID+'%' --    DROP TABLE #SudokuTree DROP TABLE #SudokuVariant --      PRINT '  - '+CONVERT(varchar(30),DATEADD(MS,DATEDIFF(MS,@StartTime,SYSDATETIME()),'19000101'),114);

Let's look at the solution found:

 --     SELECT ISNULL([1],'') [1], ISNULL([2],'') [2], ISNULL([3],'') [3], ISNULL([4],'') [4], ISNULL([5],'') [5], ISNULL([6],'') [6], ISNULL([7],'') [7], ISNULL([8],'') [8], ISNULL([9],'') [9] FROM ( SELECT c.RowID,c.ColID,f.Value FROM SudokuCell c LEFT JOIN SudokuField f ON f.CellID=c.ID ) q PIVOT(MAX(Value) FOR ColID IN([1],[2],[3],[4],[5],[6],[7],[8],[9])) p ORDER BY RowID

Other examples of solutions:

The following scripts were used to set the initial values:

View script ...

Second example:

 --   ,       TRUNCATE TABLE SudokuField GO --     INSERT SudokuField(CellID,Value)VALUES (1112,'7'),(1113,'1'),(1131,'4'),(1132,'9'), (1212,'9'),(1221,'3'),(1223,'6'), (1311,'8'),(1331,'7'),(1333,'5'), (2112,'1'),(2121,'9'),(2123,'2'), (2211,'9'),(2233,'8'), (2321,'6'),(2323,'3'),(2332,'2'), (3111,'8'),(3113,'5'),(3133,'7'), (3221,'6'),(3223,'7'),(3232,'4'), (3312,'7'),(3313,'6'),(3331,'3'),(3332,'5') GO

The third example is:

 --   ,       TRUNCATE TABLE SudokuField GO --     INSERT SudokuField(CellID,Value)VALUES (1132,'4'), (1221,'9'),(1223,'4'),(1231,'8'),(1233,'5'), (1311,'7'),(1321,'2'),(1323,'3'), (2113,'7'),(2121,'9'),(2133,'3'), (2212,'1'), (2311,'6'),(2332,'5'),(2333,'2'), (3111,'6'),(3112,'2'),(3121,'7'), (3223,'3'),(3233,'8'), (3323,'9') GO

On my computer, the solution is within 6 seconds (depending on the specified initial values):

Example 1: 4.547 sec.
Example 2: 5.317 sec.
Example 3: 3.690 sec.

Actually, everything.

The full script can be downloaded from the following link - the script .

Hope the article was interesting.

Good luck and thank you for your attention!

PS (12/04/2015)

Rewrote Oracle SQL query:

 WITH x AS( SELECT s, CHARINDEX(' ',s) ind --     --FROM (SELECT ' 15 34 89 3 2 6 8 47 9 9 2 11 2 5 9 74' s) q --FROM (SELECT ' 71 9 8 3 6 49 7 5 1 9 9 2 6 3 8 2 8 5 76 6 7 7 4 35 ' s) q FROM (SELECT ' 7 9 42 3 4 8 5 7 1 6 9 3 5262 7 3 9 8 ' s) q UNION ALL SELECT CAST(STUFF(s,ind,1,z) AS varchar(81)), --        CHARINDEX(' ',s,ind+1) --     FROM x CROSS JOIN (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) v(z) WHERE ind>0 AND NOT EXISTS( SELECT * FROM (VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9)) v(lp) WHERE z=SUBSTRING(s,(ind-1)/9*9+lp,1) OR z=SUBSTRING(s,(ind-1)%9-8+lp*9,1) OR z=SUBSTRING(s,((ind-1)/3)%3*3+(ind-1)/27*27+lp+(lp-1)/3*6,1) ) ) SELECT s FROM x WHERE ind=0

View Oracle query ...

 with x( s, ind ) as ( select sud, instr( sud, ' ' ) --from ( select ' 15 34 89 3 2 6 8 47 9 9 2 11 2 5 9 74' sud from dual ) --from ( select ' 71 9 8 3 6 49 7 5 1 9 9 2 6 3 8 2 8 5 76 6 7 7 4 35 ' sud from dual ) from ( select ' 7 9 42 3 4 8 5 7 1 6 9 3 5262 7 3 9 8 ' sud from dual ) union all select substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 ) , instr( s, ' ', ind + 1 ) from x , ( select to_char( rownum ) z from dual connect by rownum <= 9 ) z where ind > 0 and not exists ( select null from ( select rownum lp from dual connect by rownum <= 9 ) where z = substr( s, trunc( ( ind - 1 ) / 9 ) * 9 + lp, 1 ) or z = substr( s, mod( ind - 1, 9 ) - 8 + lp * 9, 1 ) or z = substr( s, mod( trunc( ( ind - 1 ) / 3 ), 3 ) * 3 + trunc( ( ind - 1 ) / 27 ) * 27 + lp + trunc( ( lp - 1 ) / 3 ) * 6 , 1 ) ) ) select s from x where ind = 0

On my computer, in terms of runtime, MS SQL is far ahead of Oracle:

Example 1: Oracle - 1.079 sec., MS SQL - 0.303 sec.
Example 2: Oracle - 2.991 seconds., MS SQL - 0.787 seconds.
Example 3: Oracle - 3.037 sec., MS SQL - 0.773 sec.

Oracle Version - 11g Enterprise Edition Release 11.2.0.1.0 - 64bit Production
MS SQL Version 2014 - 12.0.2269.0 (X64) Developer Edition (64-bit)

Source: https://habr.com/ru/post/272373/

All Articles

Use TSQL to play Sudoku

PS (12/04/2015)

More articles: