June 9, 2015 at 11:57 am
Comments posted to this topic are about the item A new set-based T-SQL solution for Sudoku puzzle
June 9, 2015 at 12:02 pm
Sorry, a correction: in the last paragraph in the first section, it should be:
Its logic is straight forward, and does NOT use any "not exists" logic....
June 12, 2015 at 2:27 pm
Another version of interest:
You might notice that, in the following update clause
UPDATEsdk SET Val=Val-(val & combo)
FROM#Sudoku AS sdk
JOIN#MapRange r on sdk.id =r.id
JOINx ON x.Range =r.Range AND Val & combo >0 AND Val - (Val & combo)>0
for each cell, it will only get updated at most once (on the first match if there is any), other impossible values (combo) for the same cell won't be taken out in this iteration. It's a kind of waste. To "fix" this, you can find all distinct impossible values and hash them into one decimal value before the update. This will ensure all found impossible values to be taken out in the same iteration, and will in turn reduce the iteration number. Below is the script. Unfortunately, when looking at the performance, it's even slower!
USE [tempDB]
GO
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
CREATE PROCEDURE [dbo].[usp_SolveSudoku_ComboBased_V2] ( @Input VARCHAR(81), @TraceFlag INT = 0 ) AS BEGIN
SET NOCOUNT ON;
IF LEN(@Input)<>81 RETURN;
DECLARE @datetime DATETIME,@UpdateCount INT, @Iterations INT;
SELECT@datetime = GETDATE(),@UpdateCount = 1, @Iterations = 0;
--=====>Setup working tables
CREATE TABLE #num( vInt INT, vBinary INT);
WITH n (vInt, vBit ) AS (
SELECT 1, 1 UNION ALL
SELECT 1+vInt, POWER(2, vInt) FROM n WHERE vInt < 9
)INSERT INTO #num SELECT * FROM n;
CREATE TABLE #Sudoku (id INT, row INT, col INT, blk INT, Val INT, NumOfValues INT);
WITH n (id, row, col, blk, val) AS (
SELECT1, 1, 1 , 1, CASE WHEN SUBSTRING(@Input,1,1)>0 THEN POWER(2, SUBSTRING(@Input,1,1)-1) ELSE 511 END
UNIONALL
SELECTid+1, id/9 +1, (id % 9) +1, (id / 27)*3 + ((id % 9)/3+1) ,
CASE WHEN SUBSTRING(@Input, id+1,1)>0 THEN POWER(2, SUBSTRING(@Input, id+1,1)-1) ELSE 511 END
FROMn
WHEREid < 81
)INSERT INTO #Sudoku (id,row,col,blk,Val) SELECT * FROM n OPTION (MAXRECURSION 80);
CREATE TABLE #Combo (Combo INT IDENTITY(1,1), NumOfChoices INT);
INSERT INTO #Combo SELECT TOP 511 0 FROM SYS.all_parameters;
UPDATE #Combo set NumOfChoices = (SELECT COUNT(*) FROM #num WHERE Combo & vBinary >0);
CREATE TABLE #MapRange (ID INT, Range INT);
INSERT INTO #MapRange SELECT ID, row FROM #Sudoku;
INSERT INTO #MapRange SELECT ID, col*10 FROM #Sudoku;
INSERT INTO #MapRange SELECT ID, blk*100 FROM #Sudoku;
--=====>Solving the puzzle
WHILE @UpdateCount >0 BEGIN
-- find all fit combo for each cell
SELECTs.id, c.combo, c.NumOfChoices
INTO#temp
FROM#Sudoku s
JOIN#Combo c ON s.val -(c.combo & s.val) = 0;
;WITH
-- Put fit combo in all three range context
a AS (SELECT m.Range, t.Combo, t.NumOfChoices FROM #temp t JOIN #MapRange m ON t.id =m.ID)
-- Find all enclosed combo in each range
,x AS (SELECT Range, combo FROM a GROUP BY Range, combo HAVING MAX(NumOfChoices) = COUNT(*))
-- gather all impossible values for each cell
,y as ( select sdk.id, (val & combo) as impossibleValues
FROM#Sudoku AS sdk
JOIN#MapRange r on sdk.id =r.id
JOINx ON x.Range =r.Range AND Val & combo >0 AND Val - (Val & combo)>0)
--find distinct impossible binary values for each cell
,z as (select distinct id, vBinary from y join #num n on y.impossibleValues & vBinary>0 )
-- aggregate the impossible binary values so we can subtract them in one-shot
,takeOut as (select ID, SUM(vbinary) as toTakeOut from z group by id)
update sdk set val = val -toTakeOut from #sudoku sdk join takeOut on takeOut.id=sdk.id
----------------------------------------------------------------------------------------------
SELECT@UpdateCount = @@ROWCOUNT, @Iterations = @Iterations+1
DROP TABLE #temp;
END
IF @TraceFlag >0 SELECT 'TotalMilliSeconds' = DATEDIFF(ms, @datetime, GETDATE()), @Iterations AS 'NumberOfIterations';
--=====>Output the Solution
UPDATE#Sudoku SET NumOfValues = (SELECT COUNT(*) FROM #num WHERE val & vBinary >0 );
WITH a AS ( SELECTRow,
Col,
v = CASE WHEN @TraceFlag = 0 AND NumOfValues > 1 THEN '_'
ELSE (SELECT LTRIM(STR(vInt)) FROM #num WHERE val & vBinary >0 FOR XML PATH('')) END
FROM#Sudoku
)SELECT * FROM a PIVOT ( MAX(v) FOR Col in ([1],[2],[3],[4],[5],[6],[7],[8],[9])) AS pvt
END
go
EXEC [usp_SolveSudoku_ComboBased_V2] '029000008030000010000520097070056100000000000006310070760041000050000020800000630' , 1
BTW, if T-SQL has a bitwise aggregation function (for "&" and "|") , the script can be more elegant and faster.
June 12, 2015 at 2:41 pm
Following is a procedural approach written in Javascript with a HTML wrapper:
<HTML><script type="text/javascript">
var currentCell, direction;
function Doit(){
currentCell=-1; direction = 1;
strSudoku=document.getElementById("Input").value;
a=strSudoku.split(''); // the working Sudoku array
b=strSudoku.split(''); // the original Sudoku array
for (i=0; i<81; i++) {a=parseInt(a);}
while (FindNextCell())
{ a[currentCell]+=1; fit=false;
while (!fit && a[currentCell]<10) // as long as not a fit and less than 10
{ if (IsValid(currentCell,a)) { fit=true; direction=1;} // if it's a fit, keep going forward
else a[currentCell]+=1; // not a fit? try next number
}
if (!fit && a[currentCell]== 10) {a[currentCell]=0; direction=-1; } //wipe the current cell and going backward
}
OutputSudoku(b, "Q", "The original Sudoku is:");
OutputSudoku(a, "A", (currentCell>80 ? "The solution is:" : "Cannot find a solution:"));
}
function FindNextCell()
{ for(var j=currentCell+direction; ;j+=direction)
{if (j>80 || j<0 ) {currentCell=j; return false;} // beyond boundary
if (b[j]=="0") // if it is an originally empty cell
{if (direction==1) {currentCell=j; return true;} // if to find forward
else { if (a[j]<9) {currentCell=j; return true;} else a[j]=0; } // if backward
} }}
function IsValid(x)
{ Xr = Math.floor(x/9)*9; //Row base
Xc = x % 9; //Column base
Xb = (Math.floor(x / 27)) * 27 + ( (Math.floor((x % 9)/3)) *3 ); //Block base
t=a[x];
for (i = 0; i < 3; i++)
{ for (j = 0; j < 3; j++)
{ if (((Xr+i*3+j) != x) && (a[Xr+i*3+j] ==t)) return false;
if (((Xc+(i*3+j)*9)!= x) && (a[Xc+(i*3+j)*9] ==t)) return false;
if (((Xb+i*9 + j) != x) && (a[Xb+i*9 + j] ==t)) return false;
} }
return true;
}
function OutputSudoku(arrSudoku, targetElement, strHeading )
{ var line = "---------+--------+--------<BR/>";
strHTML ="<BR/>"+strHeading+"<BR/>"+line;
for (i = 0; s="|", i < 9; i++) // Row i
{for (j = 0; j < 9;j++) // Column j
{s += " " + (arrSudoku==0 ? "_" : arrSudoku)+((j%3==2) ? " |" : "");}
strHTML += s + "<BR/>"+(i%3 == 2 ? line : "");
}
document.getElementById(targetElement).innerHTML=strHTML;
}
</script>
<Body><h1>Sudoku Solution</h1>
<input ID="Input" type="text" maxlength="81" size="90" name="fname" value="029000008030000010000520097070056100000000000006310070760041000050000020800000630"/>
<br/><button type="button" onclick="Doit();">Resolve</button>
<br/><table><tr><td ID="Q"></td><td width="20"></td><td ID="A"></td></tr></table>
</Body></HTML>
June 12, 2015 at 2:53 pm
Nice article. I tried it out for 2 puzzle. 1 "extreme" puzzle and looks like SQL has bug. Or I messed up the numbers but looked over it twice.
http://www.sudoku.ws/extreme-20.htm
Tried both versions and get same result
EXEC [usp_SolveSudoku_ComboBased] '600000040005002007729000003090040001000060000400080070300000165200400800050000004',1
EXEC usp_SolveSudoku_ComboBased_v2 '600000040005002007729000003090040001000060000400080070300000165200400800050000004',1
June 12, 2015 at 10:18 pm
Hi brad.mason5,
Thanks very much for your comments. You are right. I will take a look see if I can fix this.
Regards,
Kevin
July 9, 2015 at 6:33 am
Looks great. Think I'll wait a bit for you to get out any issues others find. Thanks.
April 5, 2016 at 1:34 pm
Iwas Bornready (7/9/2015)
Looks great. Think I'll wait a bit for you to get out any issues others find. Thanks.
Same for me too.
April 6, 2016 at 4:23 am
Hey Kevin! This is really great stuff pointed there! Nice idea to take care of Sudoku in SQL.
I tried your solution on the harder-hardest-sudoku-ever and it seems to not working properly, but it's really fast, though.
This post recalled me that I have an attempt to this problem a while ago. My try was to get the answer without using any recursion, loops etc. Just do it with pure-set-based solution.
So you can find what I did in Sudoku.zip. There are 2 scripts. Sudoku_create.sql creates all the objects. In the script there also are some sudoku boards you can test by truncating Sudoku. Board and inserting there a template. The second script Sudoku_query.sql - as you might guess - is the actual query that returns the solution.
I wanted to try another attempt with a little different and more normalized design of Sudoku.Board that you can find in Sudoku_2.zip. However, have not got time nor will to do this. But now - thanks to your article I actually might try again.
And also, I very like the idea of using binary algebra with #num/#combo/#maprange. I am going to check it out in my solution if you don't mind.
I will appreciate any ideas and suggestions to pure-set-based solution.
April 6, 2016 at 7:41 am
Hi Radek,
Thanks for reading this post. Seems you've done a lot on this already. I am really happy that my thoughts can contribute a little bit to your solution. I will be looking forward to it!
Regards,
Kevin Duan
April 8, 2016 at 1:09 am
On occasion I do the Sudoku in the International New York Times. This version has four additional 3x3 squares (slightly gray) inside the 9x9 puzzle area. Thus instead of 27 areas to be filled with 1-9 you have 31.
When I get a chance I will adapt your solution to this variant of the puzzle.
May 24, 2016 at 2:34 pm
Hi Scormer,
First of all, thanks for sharing, that was really interesting (and difficult...) to understand the logic behind that piece of code.
I managed to get a slight improvement on the part where you update the sudoku table. There is not much difference in the execution time (2% to 10% depending on grids and runs, but never longer than original version) but my variation usually cuts the number of iterations by about 30% 😀 .
In your code, replace lines 54-57
UPDATEsdk SET Val=Val-(val & combo)
FROM#Sudoku AS sdk
JOIN#MapRange r on sdk.id =r.id
JOINx ON x.Range =r.Range AND Val & combo >0 AND Val - (Val & combo)>0
by
, y as (
select distinct sdk.id, sdk.Val, n.vBinary
from #Sudoku AS sdk
join #MapRange r on sdk.id =r.id
join x ON x.Range =r.Range AND Val & combo >0 AND Val - (Val & combo)>0
join #num n on combo & vBinary >0
)
, z as (
select id, sum(vBinary) as combo from y group by id
)
update sdk set Val = Val-(Val & Combo)
from #Sudoku as sdk
inner join z on z.id = sdk.id
I noticed that your code uses only one (random) enclosed combo to substract it from a cell's value. The idea behind my code is to combine all the enclosed combos that can be subtstracted from the cell's value into one single combo. Since there is no easy way to bitwise-OR all the combos associated to a single cell (or at least, I don't know any), I just extract all the distinct bits (join #num) from all combos in table "y", sum them in table "z" to get the combined combo, and finally update the cell.
Test grids I used:
declare @grid char (81)
set @grid = '029000008030000010000520097070056100000000000006310070760041000050000020800000630' -- Scormer
set @grid = '600000040005002007729000003090040001000060000400080070300000165200400800050000004' -- brad.mason5 - still failing
set @grid = '800020907007100005020704000080900070604000809050006030000302060200007300703050002'
set @grid = '900570100008400000070000900103700009200906003400005201001000050000007600006023004'
set @grid = '000000700000150000056800009837040605020000070905070234400001520000032000009000000'
Viewing 14 posts - 1 through 13 (of 13 total)
You must be logged in to reply to this topic. Login to reply