TSQL Challenge 63 – Update

Categories: News, Professional, Scripts, SSC
Comments: No Comments
Published on: November 14, 2011

If you recall, I like Sudoku.  I even posted a script for solving it via TSQL.  I went so far as to enter my script into a TSQL Challenge.  That all started way back in August.  Today, I have an update!!

I was notified this morning from BeyondRelational.com that I have earned a new badge.  Cool, what’s the badge?  I clicked the link and it took me to this badge.
Huh?  I’m a winner of the SQL Sudoku Challenge?  Awesome!

Looking it over, I am winner #3.  This means I could have done better with my solution.   And looking at the other solution stats, it appears I will need to find time to see what the others did to make their solutions go sooooo fast.  I have some learning to do – woohoo.

So, now that means I need to post my solution.

[codesyntax lang=”tsql”]

[/codesyntax]

 

Sadly, that is not the most recent version of the script that I had.  I had intended on submitting this version, which is still slightly faster.

[codesyntax lang=”tsql”]

[/codesyntax]

Still, I am certain that (without having looked at the other winning solutions) this is not on par with the best solutions.  And I have a lot to learn.

TSQL Sudoku II

Categories: News, Professional, SSC
Comments: No Comments
Published on: August 23, 2011

As luck would have it, today I came across this TSQL Challenge.  It just so happens that I had already worked on a SQL Sudoku script and blogged about it less than one week ago – here.

Since posting that last article on my work on that script, I had already gone to work figuring out a few things to improve it.  One was to improve performance.  I felt it was a little slow and had an idea of what was causing it.  I’ll talk a little about that later.  The other issue was to present the output in a grid.  The first half of that was quickly solved too through a suggestion to do some string manipulation on the output.  I’ll also point that out in a bit.

If you read the Challenge from the first link, there is a requirement for it to be a grid output.  There is also what appears to be a requirement to be able to solve these puzzles through data stored in a table.  The solution I posted last week doesn’t do either of those things.  Soooo, that meant I needed to be able to do those things if I wanted to submit for this challenge.  One of the requirements was already on my to-do list – so not really that much different than my intents anyway.

For the purposes of this blog, I will only post the parts of my solution relevant to solving a puzzle from a string input.  The solution I submitted, solves from both string input as well as from table data (woot woot).

Let’s first look at the performance issue I was experiencing.  I suspected that the performance lag was related to constantly hitting back to the CTE called dual.  What I found was that there was only one very specific place that was causing the slowness.  The anchor of the recursive CTE that solves the Sudoku was referencing the dual CTE and it was dogging the performance.  The original looked like this:

[codesyntax lang=”tsql”]

[/codesyntax]

I changed it to the following and still saw the slowness.

[codesyntax lang=”tsql”]

[/codesyntax]

Finally, I decided to go ahead and whack dual from that section of code.  I had wanted to leave it because it proved useful in creating a 9 record result set.  I found a way to solve that part too – without the severe performance impact.

[codesyntax lang=”tsql”]

[/codesyntax]

This change alone was responsible for reducing the query time for a Sudoku with 30 givens from three seconds down to < 300ms.  That was a marked improvement.  I saw similar results in performance gains when working with more difficult puzzles such as those with only 19 givens.

The next thing that needed to be done was to display only the relevant data for each of the 9 rows.  Initially the solution just provides a single 81 character data string.  The fix for that is as follows.

[codesyntax lang=”tsql”]

[/codesyntax]

The code to split out the substrings was suggested to me with a minor flaw.  Each row only produced 8 digits in the result set.  This was quickly fixed by adjusting the length parameter of the substring function.  Also note that I have a Cross Apply back to the dual cte here.  This wasn’t in the original solution either.  Remember that I removed it from the anchor portion of the recursive CTE?  Well, to get the 9 record result set that I wanted, I needed to put it back somewhere.  Admittedly, this could be faster by doing a Cross Apply to a value set rather than the dual cte.  It could save a bit of memory too – I still need to test that.  Maybe I will submit another solution to the challenge with that fix if it works better.

That pretty much takes care of the performance problem as well as the first part of creating the grid.  To finish building the grid, I used a table variable and a Pivot (as I had planned).  The table variable is rather straight forward.

[codesyntax lang=”tsql”]

[/codesyntax]

I populated that Table with the following after the ctes.  Nothing real fancy here.

[codesyntax lang=”tsql”]

[/codesyntax]

This is where the code starts to get a bit fancy.  I am getting better at using the Pivot function, but sometimes it seems a bit tricky.  For instance, this time around, my numbers wouldn’t work out very well.  I figured out that the order of my columns in the Select has an impact on the Pivot as well.  Now I know.  Anyway, here is the Pivot functionality to move things into a grid.

[codesyntax lang=”tsql”]

[/codesyntax]

Not only is it important to have the columns just right, you also need to have the windowed functions done just right in order to produce a full result set.  Notice here that I do a couple Cross Apply calls.  The first is to get that Subquery result set with the pivots.  The second is using the Cross Apply against a value set.  Note that I am not using Dual in this case.  Simply put, I can’t.  I have an Insert statement between the CTEs and this Select/Pivot statement.

Another important element here is the final where clause.  This simple addition reduces my final result set from 81 records to just the 9 that I desired.  All of that, I get a grid result and the solution is done in ~40ms given the puzzle provided with the challenge.  Not too bad.

Here is the entire updated script to solve these puzzles from a string input.

[codesyntax lang=”tsql”]

[/codesyntax]

Once the challenge has been closed, I will consider revisiting this solution and posting the remainder of the script pertinent to solving a puzzle from table data.  I have adjusted my script to work for either method (from string or from a table like that in the Challenge).  I did that because I couldn’t really see somebody taking that much time to set up the data in a table in order to quickly solve the Sudoku puzzle in the Sunday paper.

 

I hope you enjoy these little improvements.

TSQL Sudoku

Comments: 9 Comments
Published on: August 17, 2011

I am a big Sudoku fan.  Typically if I need a break, I will break out a Sudoku puzzle from any of a number of different sources (Websudoku, Android Apps, Puzzle Books).  Over time, I have come across a solution here or there to solve these puzzles via TSQL.

There are a few of these solutions out there already, such as one by Itzik Ben-Gan (which I can’t get to download without the file corrupting so I still haven’t seen it), or this one on SSC (which works most of the time but does provide inaccurate results from time to time).  I still wanted something to do this via CTE (much like the solution by Itzik is described to be at the link provided – if you have that code, I want to SEE it).

Just a couple of years ago, there was a post at SSC asking for some help converting a solution from Oracle to TSQL.  I checked out that code and worked on it for a day or two.  Then I got busy with other work that replaced the pet project.  I hadn’t given the idea much thought until just a few days ago as I was browsing my Topic list I had been building for articles.

This solution stuck with me this time around and I wanted to finish it up.  The Oracle solution for whatever reason made a lot more sense to me this time around, and I made great progress quickly.  It was actually this project that I was working on that prompted another post.  While working through the solution, I learned a fair amount about both flavors of SQL.  So, in preface to continuing to read here, you may want to check out the other article real quick since it pertains to some of the conversions done in this project.

Problems First

The OP supplied the Oracle solution asking for help in creating a TSQL Solution.  Here is that Oracle version.

[codesyntax lang=”sql”]

[/codesyntax]

If you read that other post I mentioned, you will quickly identify 5 functions/objects in use in this script that just don’t work in TSQL.  Those are:  dual, instr, substr, connect by, and trunc.  I did not mention mod in my other post, but mod is also done differently in TSQL than in Oracle.  I thought this one was a bit obvious and stuck with the top 5 ;).

Solution

After figuring out some of the subtle differences between commands and the best way to approach this, I was able to come up with a TSQL solution that works.  Take not first of that last where clause in the CTE of the Oracle solution.  That clause is very similar to what I refer to as the train-stop method to get unique paths in a hierarchy.  There are several methods to do similar functionality – I have concatenated strings with Stuff as wells cast to produce this functionality.

So here goes with the first rendition of this query.

[codesyntax lang=”tsql”]

[/codesyntax]

Notice that I have chosen to use an Itzik style numbers table/CTE.  This functions as my “dual” table translation and is necessary in the remainder of the query.  The final where clause of the CTE is simplified in TSQL by simply removing the TRUNC commands.  The original solution was merely removing the decimal precision.  In TSQL, the conversion is done to INT implicitly in this case.  I need to test a few more cases, but so far it works without error.

What this does not do…

This is the first rendition of the script.  Currently, it only returns the number sequence in one big long string.  I am working on modifying this script to produce a grid layout with the solution.  I envision this will require the use of PIVOT and possibly UNPIVOT to get me close.  In addition, I expect that further string manipulation will be needed – such as stuffing commas and then splitting it to make the PIVOT/UNPIVOT easier.  I’ll have to try some things and figure it out.  Also, I expect that some explicit conversions may be best in this query.  That could help improve performance a tad.

This, to this point, has been a fun diversion.  This has helped to learn a bit about Oracle, hierarchies, and to do a little math – all in one.  Better yet is that there is still work to be done on it and more learning.  If you have ideas how to make it better – I am very interested.

page 1 of 1








Calendar
November 2017
M T W T F S S
« Oct    
 12345
6789101112
13141516171819
20212223242526
27282930  
Content
SQLHelp

SQLHelp


Welcome , today is Sunday, November 19, 2017