Log in  ::  Register  ::  Not logged in

## A set based T-SQL Solution for Sudoku Puzzle

 Author Message Kevin Duan SSC-Enthusiastic Group: General Forum Members Points: 135 Visits: 72 Comments posted to this topic are about the item A set based T-SQL Solution for Sudoku Puzzle Dave Hauze Grasshopper Group: General Forum Members Points: 11 Visits: 13 Just want to be sure I'm using this right. So, do I enter the entire puzzle number set beginning from the top left corner, reading a whole row, and then moving to the next row and continuing until I've reached the bottom right corner? Though this might seem obvious to the writer, not having this instruction may have people confused as to how to enter their puzzle problem set. mulletcheese SSC Rookie Group: General Forum Members Points: 29 Visits: 66 Hi Kevin,I really enjoyed reading your script, it was good to see TSQL used in a completely different way than usual. I would never have thought of using the bitwise operator to solve this problem. I like to see something different because seeing how other people approach a problem and write code is the best way of learning how to improve your own skills.Could you explain a bit about why you chose to work with the numbers in binary? was it your first choice or did you experiment with other ways first? The problem with sudoku is that for some of the puzzles you can only get so far by counting the numbers, eventually you may be forced to take a best guess at the content of a square. This is something that is missing from your script, do you intend to extend it in the future?I had a go by using recursion, but there is probably a better way, I modified the script to return 3 states: complete, Fail, Try Again. When the Try again state was reached the code would generate a new value for @t with one of the 0's replaced with a guess to see if that would lead to the completion of the puzzle.I identifed a square that had the minimum number of possible values and then created a new @t values for each of the possible values. I limited this to two levels of guesses.Here are the results I got for this sudoku: 080700000902000000300090020060800200750109043009004070040050009000000706000007030_ C1 C2 C3 C4 C5 C6 C7 C8 C9R1 _ 8 _ 7 3 2 9 _ _R2 9 _ 2 _ _ _ 3 _ _R3 3 _ _ _ 9 _ _ 2 _R4 _ 6 _ 8 7 _ 2 9 _R5 7 5 8 1 2 9 6 4 3R6 _ _ 9 _ 6 4 _ 7 _R7 _ 4 7 _ 5 _ _ _ 9R8 _ _ _ _ _ _ 7 5 6R9 _ _ _ _ _ 7 4 3 2_ C1 C2 C3 C4 C5 C6 C7 C8 C9R1 _ 8 _ 7 3 2 9 1 _R2 9 _ 2 _ _ _ 3 6 _R3 3 _ _ _ 9 _ _ 2 _R4 _ 6 _ 8 7 _ 2 9 _R5 7 5 8 1 2 9 6 4 3R6 _ _ 9 _ 6 4 _ 7 _R7 _ 4 7 _ 5 _ 1 8 9R8 _ _ _ _ _ _ 7 5 6R9 _ _ _ _ _ 7 4 3 2_ C1 C2 C3 C4 C5 C6 C7 C8 C9R1 5 8 6 7 3 2 9 1 4R2 9 7 2 4 8 1 3 6 5R3 3 1 4 5 9 6 8 2 7R4 4 6 3 8 7 5 2 9 1R5 7 5 8 1 2 9 6 4 3R6 1 2 9 3 6 4 5 7 8R7 6 4 7 2 5 3 1 8 9R8 2 3 1 9 4 8 7 5 6R9 8 9 5 6 1 7 4 3 2I would be very interested to see how you would solve this problem.Thanks.Ian. Kevin Duan SSC-Enthusiastic Group: General Forum Members Points: 135 Visits: 72 Hi Ian,Thanks for your posting and your detailed suggestion. It’s my pleasure to have discussion on the “ugly” script that I would never have expected anyone be patient reading through ;-) This script was created to be used in my SQL Server class to illustrate: • The new T-SQL syntax in SQL Server 2005. • The set-based approach for solving problems that have unique constraint on each set (specifically in Soduko puzzles, the rows, columns and blocks). • The performance comparison.For Soduko puzzles, there are two main types of solutions. One is iteration approach, guessing and verifying, as you suggested; the other one is set-based approach, eliminating and exclusion. Because RDBMS are very good at set-based approach, and the uniqueness constraint (in row, column and block) is a perfect scenario for using bitwise operators (using logical AND and OR to find and subtract all duplicates in one shot), I used this as a coaching example. For the purpose of illustration, I didn’t use any of the iteration methods in the script. Actually, I have the scripts using iteration approach in T-SQL, Java and JavaScript, they are posted below. In terms of bitwise operation, it’s not mandatory for the set based approach. I have a script using character string values instead of binary values(script attached below), but I needed an extra loop to implement the elimination rules. I am a big fan of binary data structure, and it's always been my first choice when applicable, say flag related problems(but unfortunately, SQL Server does not support bitmap index unless in the OLAP cube).A couple of extra notes on the set-based script: • There should be only one solution for the puzzle; otherwise the eliminations will be confused and stopped at certain point. But you can find out all solutions by using iteration approach easily. • The elimination rule has to be complete (which is not in my script, see the exception I gave in the posting. But I believe there ARE some elimination rules that can be added to make it perfect). On the performance side, SQL is faster in set-based approach than iteration approach in a lot of cases (BTW, Itzik Ben-gan's SQL books are very good resources on the in-depth SQL skill, especially in this type of comparison). But using iteration approach in procedure languages such as Java, C++ or even JavaScript is even much faster. That is why I usually strongly recommend implementing the business logic at the application (Middle) tier other than doing it inside the databases, which is the most expensive resource in the application. Scalability is also a big concern (you could have tens of application servers running the iteration code).Yes, I should have made the scripts perfect even though I just used it for teaching. If you have any good ideas or suggestions, I am more than happy to learn.Thanks,KevinFollowing is the iteration approach in T-SQL.`USE [tempdb]GOIF OBJECT_ID(N'dbo.uspSolveSudoku_2', N'P') IS NOT NULL DROP PROCEDURE dbo.uspSolveSudoku_2;GOCREATE PROCEDURE [uspSolveSudoku_2] ( @t VARCHAR(81), @Trace INT = 0 ) ASSET NOCOUNT ON DECLARE @datetime DATETIME, @ii BIGINT, @S VARCHAR(max), -- temp variable for building sql query strings @SQL1 VARCHAR(max), -- query for basic elimination rules @SQL2 VARCHAR(max), -- first query for second elimination rules @SQL3 VARCHAR(max) -- second query for second elimination rulesSET @datetime = GETDATE();------------------------------------------------------------------------------------Step 1: Setup working table #SDK.CREATE TABLE #SDK ( i INT, -- Working table, one record per cell, with row/column/block lable and current possible values--DECLARE #SDK TABLE ( i INT, -- Working table, one record per cell, with row/column/block lable and current possible values r INT, -- Row # c INT, -- Column # b INT, -- Block # v INT);WITH n (i, r, c, b, v) AS ( SELECT 1, 1, 1 , 1, CASE WHEN substring(@t,1,1)>0 THEN -CONVERT(int, substring(@t,1,1)) ELSE 0 END UNION ALL SELECT i+1, i/9 +1, (i % 9) +1, (i / 27)*3 + ((i%9)/3+1) , CASE WHEN substring(@t, i+1,1)>0 THEN -CONVERT(INT, substring(@t, i+1,1)) ELSE 0 END FROM n WHERE i < 81) INSERT INTO #SDK (i,r,c,b,v) SELECT * FROM n OPTION (MAXRECURSION 80); DECLARE @i INT, @STEP INT, @V INT, @R INT, @C INT, @B INT, @P TINYINTSELECT @i = 1, @STEP = 1, @ii = 0WHILE @i>0 AND @i<82 BEGIN SET @ii = @ii+1 IF @Step<>0 SELECT @V = V, @R = R, @C = C, @B = B FROM #SDK WHERE i= @i -- Given cell, go forward or backward to skip IF @V <0 BEGIN SELECT @i = @i + @Step END ELSE -- Already hit max, reset to zero and getting backward IF @V=9 BEGIN UPDATE #SDK SET v=0 WHERE i= @i SELECT @Step = -1, @i = @i - 1 END ELSE BEGIN SET @v = @v +1 UPDATE #SDK SET v = @V WHERE i= @i IF EXISTS (select * FROM #SDK WHERE i<>@i AND ABS(v)=@V AND (r=@r OR c= @c OR b= @b)) BEGIN SET @Step = 0 END ELSE BEGIN SELECT @Step = 1, @i=@i+1 END END -- SELECT @step IF @ii = -1 GOTO OutputSudoku ENDSELECT @ii ------------------------------------------------------------------------------------Step 4: Output the SolutionOutputSudoku: -- you can add "GOTO OutputSudoku" anywhere above to stop the calculation and see the interim results!WITH a AS ( SELECT r AS 'Row', c, v FROM #SDK ) SELECT * FROM a pivot ( max(v) for c in ([1],[2],[3],[4],[5],[6],[7],[8],[9]) ) AS pSELECT DATEDIFF(ms, @datetime, GETDATE())GOEXEC uspSolveSudoku_2 '080001000030750000100000027000004301400000006701300000520000004000049070000800090',1 -- an evil level puzzle--EXEC uspSolveSudoku_2 '080700000902000000300090020060800200750109043009004070040050009000000706000007030',1--EXEC uspSolveSudoku_2 '200060000000900871740008006006080030003000100090030400300700018972005000000090002' , 1--EXEC uspSolveSudoku_2 '200060000000900871740008006006080030003000100090030400300700018972005000000090002' ,1--EXEC uspSolveSudoku_2 '029000008030000010000520097070056100000000000006310070760041000050000020800000630' , 1--EXEC uspSolveSudoku_2 '080700000902000000300090020060800200750109043009004070040050009000000706000007030',1--EXEC uspSolveSudoku_2 '060104050008305600200000001800407006006000300700901004500000002007206900040508070',1-- Code Cleaning:`Following is the iteration approach in JavaScript.`//Create two arrays:// a: Holds the puzzle value.// b: Holds the predefined flag(non-zero)a = new Array(0,0);b = "060590004"+"005004302"+"290700100"+"000017238"+"400000006"+"378920000"+"002001049"+"507600800"+"800035010";for (i = 0; i < b.length; i++){ a[i] = parseInt(b[i]);}//Loop through each none predefined cellL: for (k = FindNext(-1); k while (a[k]+= 1 ){ if (a[k] == 10){ if ((k = GoBack(k))== -1){ document.write("Cannot find solution!!"); break L; } } Else{ if (Validate(k)){ if ((k = FindNext(k)) == -1){ // solution found ! document.write("Found solution"); document.write(a); break L; } } } } }// Sets the pointer to the next non-predefined cell after cell i,// returns -1 when goes beyond the boundary.function FindNext(i){ for(j=1;;j++){ if (i+j== b.length ) return -1; if (b[i+j]==0) return i+j; } }//Sets the pointer back to the last increasable non-predefined cell,// meanwhile, sets the values of the passed cells to zero,// returns -1 when goes beyond the boundary.function GoBack(i){ a[i] = 0; while (--i >= 0){ if (b[i]==0){ if (a[i]<9){ return i;} else{ a[i] = 0; } } } return -1;}//Validate the cell xfunction Validate(x){ xr = Math.floor(x/9)*9; //Row offset xc = x % 9; //Column offset xb = (Math.floor(x / 27)) * 27 + ( (Math.floor((x % 9)/3)) *3 ); //Block offset for (i = 0; i < 3; i++){ for (j = 0; j < 3; j++){ if ((((Xr+i*3+j) != x) && (a[Xr+i*3+j] ==a[x])) || (((Xc+(i*3+j)*9)!= x) && (a[Xc+(i*3+j)*9] ==a[x])) || (((Xb+i*9 + j) != x) && (a[Xb+i*9 + j] ==a[x]))) return false; } } return true;} `Following is the iteration approach in Java.`public class Sudoku { public int[][] s = { {0,0,9,0,2,8,0,0,0}, {0,0,0,7,0,0,0,0,2}, {0,0,0,0,0,0,1,3,4}, {0,0,0,0,6,0,0,2,8}, {8,0,0,0,4,0,0,0,9}, {3,5,0,0,7,0,0,0,0}, {6,8,4,0,0,0,0,0,0}, {9,0,0,0,0,1,0,0,0}, {0,0,0,5,9,0,7,0,0} }; private int[][] f = new int[9][9]; public int row = 0, col = -1; private String msg = "Still Trying..."; public void solveIt(){ for (int i = 0; i < 9; i++){ for (int j = 0; j < 9; j++){ f[i][j]=s[i][j]; } } while (moveNext()){ while (!this.findNextNumber()) { if (s[row][col]==10){ if (!moveBack()){ msg = "No Solution Found"; return; } } } } msg = "Congratulations! Found Solutions!"; } private boolean findNextNumber(){ while (++s[row][col]<=9) { if (checkCell()) {return true;} } return false; } private boolean moveNext(){ do { if (++col ==9) {row++; col = 0;} } while ( row<9 && f[row][col]!=0); return (row<9?true:false); } private boolean moveBack(){ s[row][col]=0; do { if (--col == -1) {row--; col = 8;} } while ( row>=0 && f[row][col] != 0); return (row < 0 ? false : true); } private boolean checkCell(){ for (int i = 0 ; i < 9; i++){ if (i != col && s[row][i]==s[row][col]) return false; if (i != row && s[i][col]==s[row][col]) return false; } for (int i = row/3*3 ; i < row/3*3+3; i++){ for (int j = col/3*3 ; j < col/3*3+3; j++){ if (!(i == row && j == col) && s[i][j]==s[row][col]) return false; } } output(); return true; } public void output(){ System.out.println(msg); for (int i = 0 ; i < 9; i++){ for (int j = 0 ; j < 9; j++){ System.out.print(s[i][j]); }; System.out.println(""); }; } public static void main(String[] args){ Sudoku mySudoku = new Sudoku (); mySudoku.solveIt(); mySudoku.output(); }}`Following is the T-SQL set-based solution for character flags (vs. bitwise values) `IF OBJECT_ID(N'dbo.uspSolveSudoku_C', N'P') IS NOT NULL DROP PROCEDURE dbo.uspSolveSudoku_C;GOCreate procedure dbo.uspSolveSudoku_C ( @t varchar(100), @Trace bit = 0 ) ASSet nocount ondeclare @datetime datetime; select @datetime = getdate();-----------------------------------------Step 1: Setup working table #s. -- r for Row#, -- c for Column#, -- b for Block#, -- v for Value-- d for current # of possible values---------------------------------------Create table #s (i int, r int, c int, b int, v varchar(9), d as len(v));WITH n (i, r, c, b, v) AS ( SELECT 1, 1, 1 , 1, case when substring(@t,1,1)>0 then substring(@t,1,1) else '123456789' end UNION ALL SELECT i+1, i/9 +1, (i % 9) +1, (i / 27)*3 + ((i%9)/3+1) , case when substring(@t, i+1,1)>0 then substring(@t, i+1,1) else '123456789' end from n where i < 81)insert into #s (i,r,c,b,v) select * from n OPTION (MAXRECURSION 80); -----------------------------------------Step 2: Create sequential number-----------------------------------------Create table #num ( vInt int, vBinary int);WITH n (i ) AS ( SELECT 1 UNION ALL SELECT i+1 from n WHERE i < 9) select convert(char(1), i) as P into #num from n -----------------------------------------Step 3: Solve the puzzle. A "range" means a single row, column or block---------------------------------------Declare @SQL varchar(2000), @SQL1 varchar(2000), @SQL2 varchar(2000), @SQL3 varchar(2000) -- query to eliminate determined values from un-determined cells in the same rangeSet @SQL1 = 'while @@rowcount >0 begin update #s set v = replace(#s.v, b.v, '''') from (select Range, v from #s where d = 1) as b where #s.Range= b.Range and #s.d >1 and charindex(b.v, #s.v)>0; end;'-- query to determin the cell that solely contains a possible value in the same rangeSet @SQL2 = 'Update #s set v = pfrom ( select Range, p from #s cross apply (select P from #num where charindex(#num.p, #s.v)>0) as n where d >1 group by Range, p having count (*) =1 ) as twhere #s.Range = t.Range and #s.d >1 and charindex (p, #s.v) >0; '-- if 2 cells in the same range have the same pair of possible values, eliminate the pair of values from other cells in the same rangeSet @SQL3 = 'Update #s set v = replace(replace(v, substring(v2,1,1), ''''),substring(v2,2,1), '''')from ( select Range, v as v2 from #s where d = 2 group by Range,v having count(*) =2 ) as twhere #s.Range = t.Range and #s.d>1 and (charindex(substring(v2,1,1), #s.v)>0 or charindex(substring(v2,2,1), #s.v)>0) ; ' Declare @Count1 smallint, -- Count of determined cells, before updates @Count2 smallint, -- Count of determined cells, after updates @CountSecondRuleExecTimes int ;Select @Count1 = 0, @CountSecondRuleExecTimes = 0;Select @Count2 = Count(*) from #s where d=1While @Count2 < 81 and @CountSecondRuleExecTimes < 100 Begin While @Count1 <> @Count2 and @Count2 < 81 Begin Select @Count1 = count(*) from #s where d = 1 Set @SQL = replace(@SQL1, 'Range','r'); Exec (@SQL); If @Trace= 1 print Char(13)+Char(10)+@SQL Set @SQL = replace(@SQL1, 'Range','c'); Exec (@SQL); If @Trace= 1 print Char(13)+Char(10)+@SQL Set @SQL = replace(@SQL1, 'Range','b'); Exec (@SQL); If @Trace= 1 print Char(13)+Char(10)+@SQL Select @Count2 = count(*) from #s where d = 1 End If @Count2 < 81 Begin Set @SQL = replace ( case when (@CountSecondRuleExecTimes % 6) <3 then @SQL2 else @SQL3 end, 'Range', case (@CountSecondRuleExecTimes % 3) when 0 then 'r' when 1 then 'c' when 2 then 'b' end) If @Trace= 1 print Char(13)+Char(10)+@SQL; Exec (@SQL); Select @Count2 = count(*) from #s where d = 1 Select @CountSecondRuleExecTimes = @CountSecondRuleExecTimes + 1 if @Count1<> @Count2 AND @Trace = 1 Print replace(@SQL, char(13)+char(10),'') EndEnd ;---------------------------------------OutputSudoku:---------------------------------------with a as ( select r , c, v from #s ) select * from a pivot ( max(v) for c in ([1],[2],[3],[4],[5],[6],[7],[8],[9]) ) as p;If @Trace = 1 select datediff(ms, @datetime, getdate()), @CountSecondRuleExecTimesGOexec uspSolveSudoku_C '200060000000900871740008006006080030003000100090030400300700018972005000000090002' , 1` Kevin Duan SSC-Enthusiastic Group: General Forum Members Points: 135 Visits: 72 Hi Dave,Sorry for my overly simplied comments. Yes, you are right. The input string is composed by the contents in the cells, from left to right, from top to the bottom, it should be exactly 81 characters in length. For non-predefined (empty) cells, use 0's. You can jump to the output script at the bottom anywhere after the input is read, to see the puzzle values.Thanks,Kevin Iwas Bornready One Orange Chip Group: General Forum Members Points: 29546 Visits: 885 This looks like fun.

## Permissions

 You can't post new topics. You can't post topic replies. You can't post new polls. You can't post replies to polls. You can't edit your own topics. You can't delete your own topics. You can't edit other topics. You can't delete other topics. You can't edit your own posts. You can't edit other posts. You can't delete your own posts. You can't delete other posts. You can't post events. You can't edit your own events. You can't edit other events. You can't delete your own events. You can't delete other events. You can't send private messages. You can't send emails. You can read topics. You can't vote in polls. You can't upload attachments. You can download attachments. You can't post HTML code. You can't edit HTML code. You can't post IFCode. You can't post JavaScript. You can post emoticons. You can't post or upload images.

##### Select a forum
 SQL Server 2016      SQL Server 2016 - Administration      SQL Server 2016 - Development and T-SQL SQL Server 2014      Administration - SQL Server 2014      Development - SQL Server 2014 SQL Server 2012      SQL 2012 - General      SQL Server 2012 - T-SQL SQL Server vNext      SQL Server 14 - Administration      SQL Server 14 - Development SQL Server 2008      SQL Server 2008 - General      T-SQL (SS2K8)      June 2007 CTP      Working with Oracle      July CTP      SQL Server Newbies      Security (SS2K8)      SQL Server 2008 High Availability      SQL Server 2008 Administration      Data Corruption (SS2K8 / SS2K8 R2)      SQL Server 2008 Performance Tuning Cloud Computing      SQL Azure - Development      SQL Azure - Administration      Amazon AWS and other cloud vendors      General Cloud Computing Questions Reporting Services      Reporting Services      Reporting Services 2005 Administration      Reporting Services 2005 Development      Reporting Services 2008/R2 Administration      Reporting Services 2008 Development      SSRS 2012      SSRS 2014      SSRS 2016 Programming      Connecting      General      SMO/RMO/DMO      XML      Service Broker      Powershell      Testing      TFS/Data Dude/DBPro      SSDT      Continuous Integration, Deployment, and Delivery      R Services and R Language Data Warehousing      Integration Services      Strategies and Ideas      Analysis Services      Data Transformation Services (DTS)      Performance Point      Data Mining      PowerPivot      R language      Machine Learning Database Design      Disaster Recovery      Design Ideas and Questions      Relational Theory      Hardware      Virtualization SQLServerCentral.com      Anything that is NOT about SQL!      Contests!      Editorials      SQLServerCentral.com Announcements      SQLServerCentral.com Website Issues      Suggestions      Tag Issues with Content      Podcast Feedback      SQLServerCentral.com Test Forum      Articles Requested SQL Server 2005      Administering      Backups      Business Intelligence      CLR Integration and Programming.      Data Corruption      Development      Working with Oracle      SQL Server 2005 Compact Edition      SQL Server 2005 General Discussion      SQL Server 2005 Security      SQL Server 2005 Strategies      SS2K5 Replication      SQL Server Express      SQL Server 2005 Performance Tuning      SQL Server 2005 Integration Services      T-SQL (SS2K5)      SQL Server Newbies SQL Server 7,2000      Administration      Backups      Data Corruption      General      Globalization      In The Enterprise      Working with Oracle      Security      Strategies      SQL Server Newbies      Service Packs      SQL Server CE      Performance Tuning      Replication      Sarbanes-Oxley      T-SQL      SQL Server Agent SQL Server and other platforms      MySQL      Oracle      PostgreSQL      DB2      SQL Server and Sharepoint Older Versions of SQL (v6.5, v6.0, v4.2)      Older Versions of SQL (v6.5, v6.0, v4.2) Career      Certification      Employers and Employees      Events      Job Postings      Resumes and Job Hunters      Presentations and Speaking      Retired Members Testing Center      Question of the Day (QOD)      SQL Server Security Skills Microsoft Access      Microsoft Access Products and Books      Third Party Products         CA         Extreme Technologies.         Innovartis         Embarcadero         SQL Sentry         Sonasoft         SQLCentric         Golden Gate Software         Lumigent         Red Gate Software         Quest Software         ApexSQL         Idera      Discussions about Books         Discuss Programming Books          Discuss XML Books          Discuss T-SQL Books          Discuss Data Warehousing Books          Discuss DTS Books          Discuss SQL Server 7.0 Books         Discuss SQL Server 2000 Books Notification Services      Administration Article Discussions Future Versions      SQL 12

## Search

 Copyright © 2002-2017 Redgate. All Rights Reserved. Privacy Policy. Terms of Use. Report Abuse.