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

Get your favourite SSC scripts directly in SSMS with the free SQL Scripts addin. Search for scripts directly from SSMS, and instantly access any saved in your SSC briefcase from the favorites tab.
Download now (direct download link)

A Sudoku solution with set based T-SQL utilizing binary operators

By Kevin Duan,

The table numBinaryDigits is an auxiliary table that stores all possible values (1~9) and their corresponding binary values in this solution.


The UDF udfConvertBinaryToDecimalString converts a binary value to the comma delimited decimal list, just to help the output.

In the stored procedure uspSolveSudoku:

  1. There are three elimination rules, as listed below. The first rule will be considered as first method, the last two will be considered as second method. Each time after a second method is applied, the first method will be applied until no newly determined cells found.
    • Rule 1: Eliminate determined values from un-determined cells in the same range
    • Rule 2: Determine the cell that solely contains a possible value in the same range
    • Rule 3: If two cells in the same range have and only have the same pair of possible values, eliminate the pair of values from other cells in the same range
  2. The first parameter @T should be the original puzzle in string format of 81 characters in length, 0 for empty cells
  3. The second parameter @Trace is a flag to ease the trace of code execution, showing how many times any of second elimination methods have been executed and the overall execution time. If the flag is on, the second elimination method queries will also be printed in the message pane.
  4. Dynamic queries are used just to make the logic more readable, and could be replaced by static queries, which will increase the performance by 30-40% based on my test.
  5. In the dynamic queries, the "Range" refers to a row, a column or a block which will be replaced by "r", "c" or "b" just before execution.
  6. You might want to add "goto OutputSudoku" at the place where you want to stop the execution to see the interim result.

You might also want to play around with this solution by switching to table variable or physical table instead of using temporary table (#s). For using table variable, you have to make the table visible to the dynamic queries or change to using static queries. For using physical table, you can also try to use a persisted computed column instead of column "d". In this case, you need to create a function WITH SCHEMABINDING that gives the number of possible values for the v column value in the same row, the same result as "select count(*) from numBinaryDigits where (v & vBinary)>0". This could also increase the performance a bit, but not too much.

Total article views: 3479 | Views in the last 30 days: 3
 
Related Articles
FORUM

eliminating duplicates

eliminating duplicates

FORUM

Partition Elimination with Varaiable in Query

No partition elimination with sprocs?

FORUM

query execution order

query execution order

FORUM

Query Execution Performance

Query Execution Performance

FORUM

Help reqd for eliminating a similar IDs- Query

Help reqd for eliminating a similar IDs- Query

Tags
advanced querying    
games    
miscellaneous    
puzzle    
sql server 2005    
t-sql    
 
Contribute

Join the most active online SQL Server Community

SQL knowledge, delivered daily, free:

Email address:  

You make SSC a better place

As a member of SQLServerCentral, you get free access to loads of fresh content: thousands of articles and SQL scripts, a library of free eBooks, a weekly database news roundup, a great Q & A platform… And it’s our huge, buzzing community of SQL Server Professionals that makes it such a success.

Join us!

Steve Jones
Editor, SQLServerCentral.com

Already a member? Jump in:

Email address:   Password:   Remember me: Forgotten your password?
Steve Jones