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,
Kevin
Following is the iteration approach in T-SQL.
USE [tempdb]
GO
IF OBJECT_ID(N'dbo.uspSolveSudoku_2', N'P') IS NOT NULL DROP PROCEDURE dbo.uspSolveSudoku_2;
GO
CREATE PROCEDURE [uspSolveSudoku_2] ( @t VARCHAR(81), @Trace INT = 0 )
AS
SET NOCOUNT ON
DECLARE@datetime DATETIME,
@ii BIGINT,
@s-2 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 rules
SET@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 (
SELECT1, 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 0 AND @i<82 BEGIN
SET @ii = @ii+1
IF @Step0 SELECT @v-2 = V, @r = R, @C = C, @b-2 = B FROM #SDK WHERE i= @i
-- Given cell, go forward or backward to skip
IF @v-2 <0 BEGIN
SELECT @i = @i + @Step
END
ELSE
-- Already hit max, reset to zero and getting backward
IF @v-2=9 BEGIN
UPDATE #SDK SET v=0 WHERE i= @i
SELECT @Step = -1, @i = @i - 1
END
ELSE
BEGIN
UPDATE #SDK SET v = @v-2 WHERE i= @i
IF EXISTS (select * FROM #SDK WHERE i@i AND ABS(v)=@V AND (r=@r OR c= @C OR b= @b-2)) BEGIN
SET @Step = 0
END
ELSE BEGIN
SELECT @Step = 1, @i=@i+1
END
END
--SELECT @step
IF @ii = -1 GOTO OutputSudoku
END
SELECT @ii
----------------------------------------------------------------------------------
--Step 4: Output the Solution
OutputSudoku: -- you can add "GOTO OutputSudoku" anywhere above to stop the calculation and see the interim results!
WITH a AS (SELECTr 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 p
SELECT DATEDIFF(ms, @datetime, GETDATE())
GO
EXEC 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 = parseInt(b);
}
//Loop through each none predefined cell
L: for (k = FindNext(-1); k= 0){
if (b==0){
if (a<9){ return i;}
else{
a = 0;
}
}
}
return -1;
}
//Validate the cell x
function 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[j]=s[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=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]==s[row][col]) return false;
if (i != row && s[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[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 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 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 range
Set @SQL2 =
'Update #s set v = p
from ( 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 t
where #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 range
Set @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 t
where #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=1
While @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),'')
End
End ;
---------------------------------------
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()), @CountSecondRuleExecTimes
GO
exec uspSolveSudoku_C '200060000000900871740008006006080030003000100090030400300700018972005000000090002' , 1