Search results matching tag 'Fun'

Trigger Authoring Decision Tree

merrillaldrich — Wed, 06 Mar 2013 18:46:09 GMT

PASS Summit 2011 - What you can expect at the Conference - Summary

RickHeiges — Mon, 19 Sep 2011 13:30:00 GMT

As I finish up preparing for the Sep 20 (@1pm ET) webcast, I thought a final blog post may be appropriate in order to quickly reference many of the areas that I have touched upon. Naturally, much of this information is geared towards First Timers, but Alumni are welcome to join in the webcast as well and are encouraged to help spread even more tips/tricks around to all who attend.

PASS Summit 2011 - What you can expect at the Conference - Part 7

RickHeiges — Fri, 16 Sep 2011 16:30:00 GMT

I really don't think that you can get the full flavor of the Summit unless you delve into Social Networking. There are multiple vehicles for social networking. Twitter, Facebook, Foursquare, LinkedIn, and Yelp are all tools in the Social Networking Toolbox. At the Summit, the best one of these is Twitter. With twitter, yo can eavesdrop on conversations, get tips in real time, and find out where people are hanging out at.

Here is a YouTube video that is pretty good about Twitter. There are other ones out there as well.

I recommend that you use a twitter client like TweetDeck on your PC and also on your smart phone. The interface makes it easier to use than the plain vanilla web page. In your twitter client, you can create custom "feeds" to target a particular word or idea. You can have multiple comuns on your client with many of these "feeds" that you follow. These words that you target are often referred to as hashtags. Here are some common hashtags to follow:

#sqlpass
#sqlhelp
#firsttimers
#sqlkilt
#sqlkaraoke
#24hop
#sqlrally
#sqlsat

Once you start using twitter, you''ll understand more of what all this means. Brent Ozar has put together a great primer on twitter that may be found here. Closing thoughts on Twitter:

You don't have to create an account to get value out of it. You can just follow some of the hashtags listed above - especially #sqlpass
Get on twitter and try it out before you get to the summit
Follow #sqlhelp and learn a LOT about where you can find great resources for SQL Server.
make up your own hashtags like #JustSayin or #KilroyWashere or #whatever
When choosing a "handle", consider incorporating "SQL" as part of it. Members of the SQL Community are more apt to follow you and value your tweets if they know you are a SQL Server Professional.

Another application (targeted for mobile devices) that can be valuable is FourSquare. FourSquare also integrates with Twiiter and FaceBook. It works best with smart phones with GPS enabled. Essentially, you check-in to a location such as a restaurant , bar, Conference Center, etc. As part of the "check-in" process, you can add a "shout" to your check-in that may be tweeted and/or set to update your FaceBook status. This is optional, but it can help with networking. Check out FourSquare.

The third social networking property that holds value is LinkedIn. There are many discussion groups affiliated with PASS. It is a great way to connect with other SQL Professionals once you get home.

There is also a PASS YouTube Channel. Check out the videos from last year's summit! Of course, PASS is also on FaceBook. Another social networking tool that you may find useful is YELP. It is particualrly good at helping to find a good restaurant near by.

Flickr - Many folks who are shutterbugs or just want to share photos do so via Flickr and the #sqlpass or #PASS2011 hashtags. I look forward to seeing a lot of pictures from everyone this year.

Bottom Line: Get on Twitter Now! Follow #sqlpass and #sqlhelp. Get involved in the conversation.

PASS Summit 2011 - What you can expect at the Conference - Part 2

RickHeiges — Mon, 12 Sep 2011 13:11:00 GMT

One of the things that you should do is map out your "Learning Itinerary" before coming to the summit. It probably will change once you get onsite, but having a plan will save you time and perhaps some frustration. You can go to the Summit website and start to build your schedule.

When you arrive at registration to get your badge and other materials, you will also receive a Program Guide. This booklet has a lot of information about the entire event. It has a detailed description of each session, maps of the venue, and much more. We also have a Smart Phone App (iPhone, Android, Windows 7 Phone) that has much of this same information. The advantage of relying on the Smat Phone App is that it will have the latest information available (Session Changes, etc). More information on this later.

Each Session has a Session Code associated with it. Example: AD-104, BIA-303-S, DBA-302-M. There are 4 timeslots/day with up to 15 different choices; that's over 170 choices!

The first part identifies the Track the session is part of:

AD = Application Development
AZ = SQL Azure
BIA = BI Architecture / Development
BID = BI Deployment / Delivery
DBA = Enterprise Database Administration and Deployment
PD = Professional Development

The Second part indicates the Level that the session is aimed at. 100, 200, and so on.

The suffix is optional and may indicate several things to be aware of:

S = Spotlight Session (These sessions are 90 minutes instead of 75)
M= Microsoft (Presented by Microsoft)
C = CSS (Presented by a Member of the CSS team from Microsoft)
HD = Half-Day (3 hour session - NEW This Year!)

There are also a few sessions identified as "Lightning Talks" These sessions have a variety of speakers who give a brief 5 minute presentation. Lots of Fun and covers a multitude of subjects quickly. You won't be bored in here! I encourage you to attend at least one Lightning Talk during the summit. You never know what gems you can find in a 5 minute talk.

What happens if there is more than one session that you wish to attend? Can you be two places at once? No, but all sessions are being recorded and will be available usually a few weeks later via streaming. A DVD set may also be purchased by modifying your registration information or by ordering onsite.

Outside the session rooms, a sign will indicate what sessions are scheduled to be there and who is presenting. Some sessinos / speakers will have a special designation. Here are some terms that you may see and what it means:

MVP - Microsoft Most Valuable Professional Awardee (This is a non-Microsoft person who eagerly shares knowledge about SQL Server with the community)
MCM - Microsoft Certified Professional (Passed both a written and Lab Exam)
SQLCAT - SQL Server Customer Advisory Team member (often weearing a SQLCAT shirt typically of a hideous color)

In the hallways and lunch rooms, you will also see people with a Red Vest on. These people are playing the role of a PASS Ambassador. These people are Alumni Attendees who simply want to help you have a better experience at the summit. They can help you with Finding a Session room, Reading the Program Guide, Getting you in touch with the right resource, or just about anything else.

The Session Rooms are setup "Theater Style" - Rows of chairs beside one another (no tables). You will notice that each session room will have several reserved seats for Amabassadors. Ambassadors often come in late or leave a little early and need easy access to alleviate any disruption to the speaker.

Each Room also has a Room Monitor. These people work for the convention center. They are charged with:

Enforcing Capacity Restrictions / Fire Code
Enforcing Security for Entry to the Session Rooms by checking badges
Counting Attendees / Providing a 5 minute warning to the speaker
Collection Paper Evaluations

Room Monitors are helpful too - especially with questions about the facility. Amabassadors are a better resource for questions relating to PASS or the summit in general.

Setting up for PASS Summit Orientation

RickHeiges — Wed, 31 Aug 2011 13:41:00 GMT

I am in the process of finalizing a date (week of Sep 19) for a LiveMeeting event that will focus on the upcoming PASS Community Summit. It will be primarily targeted at the first-timers to the Summit, but everyone will be welcome to join. There will be event information forthcoming on the PASS website - www.sqlpass.org.

Here is a rundown on the topics that I plan to cover:

What is PASS? PASS Events (Summit, Rally, 24hop, SQLSat, Chapters, Virtual Chapters)
What to Expect / How to read the Program Guide and Smart Phone App to Plan your Itinerary
Pre-cons, half-day sessions, spotlight sessions, Speaker annotations (MVP, MCM, SQLCAT)
Stuff besides Sessions (Hands-on labs, SQL Clinic, Expert Pods, Birds of Feather Lunch, etc.)
Social Media (Twitter, Foursquare, Flickr, etc)
Activities "outside of the Summit" (SQL Karaoke, Photo walk, Kilt Day, etc)
Logistics - Getting to the Summit from SEA-TAC (light rail, shuttle, cab, etc.)

I have gone through the Flickr photos. Always looking for more "gems". Looking for photos that may help with logistics or showcasing interaction at the summit. Leave a comment for a link to other sites like Flickr with pictures from past summits.

Thanks!

Chasing the ISV, or, “That code makes my teeth hurt.” T-SQL Tuesday (ish) #21

merrillaldrich — Wed, 10 Aug 2011 14:00:00 GMT

This month’s T-SQL Tuesday – a blog party dreamed up by sqlblog.com’s Adam Machanic ( blog | @AdamMachanic ) – is about that code we’ve all written that we don’t really like to think about too often. You know the stuff. I can’t help but imagine the next poor guy who comes across some of mine and thinks, “What the … How in … Seriously?”

I have two gems to share today. They share the theme, “Chasing the ISV,” because they are both SQL Agent jobs that essentially follow ISV code and constantly, 24 x 7, mop up problems with applications.

The first example I’ll put up here is one I blogged about briefly last year. We had an ISV system that was riddled with pretty horrible triggers, which I was hesitant to touch for fear of the “Jenga effect.” Pull just one line of trigger code out and – who knows?

Said system had a production issue because a value stored in two places, that was supposed to match (winning system here) no longer did. I discovered that the underlying reason was that the tables in play had triggers that could not handle a set of rows, but just one row at a time – a too-common anti pattern.

IF Problem GOTO Workaround

So, what to do. Production issue. Deep breath. Here goes:

Again:

UPDATE TOP (1) dbo.someTable SET field3 = 'NEW'
WHERE field2 = 'NEW' AND field3 = ''

IF @@ROWCOUNT > 0 GOTO Again

Into a SQL Agent job with that, executed once every few minutes.

So. Wrong.

Also fixed the issue. And it’s still in use, I believe. I try not to think about it.

IN ( Pain, Suffering )

The second bit of pure awesome I have to offer today takes a bit more explanation. I think I should anonymize this one to protect the guilty. (That first example has, believe it or not, the real column names.)

Another ISV provided a system to one of my past employers that, let’s say for argument, provided a web application to manage distributed offices in locations all over the country. The structure of the system required that people at the company be able to view one or a few of these locations’ data, but not the data from other locations. So the system had a row-level security mechanism to filter the data by groups - a fairly standard idea, but theirs was not a typical implementation at all. The way the initial version of this software operated was, roughly:

An administrator for the application would change some aspect of the security groups using the web application.
The system would, upon clicking Submit, create (or recreate) one or several view definitions, inside of which there was a SELECT with a static IN (,,) list of any and all the locations that a given group or individual could see on the system. The view would provide the row-level security. The IN(,,) list could have a few or hundreds of items. A classic data-as-code anti-pattern.
The system was very busy, so altering the view would often fail or cause … “side effects.”

The company actually instituted a rule that security changes like this could only be made after hours, and made staff stay late to do that work. If this happened during the day, the system would generally grind to a halt, and none of the 1,000 or so concurrent users could do anything. Why? The IN() lists in these views could have hundreds of values, and they worked against millions of rows of data. That meant that with no meaningful stats to work with about these embedded lists, the query optimizer would always pick a terrible query plan for vital processes on the system.

The ISV almost fixed this problem. Nearly.

When complaints surfaced, they went in and added a more scalable feature that would use a many-to-many table to store the security relationships. The table could be indexed, and would have stats, which was wonderful, and it solved the performance issue.

When they used it.

Here’s the rub: the were so fearful about disrupting their customers’ existing deployments – a noble but ultimately doomed posture – that they kept the old view mechanism too. Any old features of the product used the old system, while new or rewritten features used the new system. Now their code had to maintain both systems, and attempt to be sure they matched. Which they did. Mostly. Except that time we had to have one of their developers spend a week untangling the thing. But I digress.

If I recall, and this was a few years ago, so I may have this wrong, it seems like their first table-based implementation didn’t exactly work, and they had to create a second one, and then they kept all three systems, with some massive stored procs to keep them all in sync. And the proc worked, except when there was a logic problem like duplicate rows in the tables, and then it didn’t anymore.

ALTER VIEW dbo.FixMe

This is where our little DBA group came flying in with our superhero capes and a brilliant, yet horrible, workaround. I can’t quite remember who created this, so my apologies if I cannot credit the specific individual, but I know I, erm, “tuned” it over the years. I also vividly remember the phone calls and the shouting when this workaround was not operating as designed.

We made a SQL Agent job to run every few minutes. The code for the job was, essentially:

Examine the text for all the views in the database, via syscomments, where the view name matched some text pattern that makes it look like one of these security views.
If the view definition contains one of these IN(,,) clauses then rewrite the view, via dynamic SQL, as a join between the security tables.

Like the example above, this job would basically sit there and chase the underlying system, and if a security change was made, it would locate the offending view definition and rewire it on the fly to use the more performant and optimizer-friendly tables.

I think the vendor has since fixed the view definition issue. Happily, I don’t have to work on this system any longer, so I can’t say whether the views themselves persist to this day.

Here’s the code, unvarnished but anonymized. I found it on an old flash drive:

IF EXISTS ( SELECT * FROM syscomments sc1    
   INNER JOIN sysobjects so ON so.id = sc1.id   
   WHERE so.type ='V'    
      AND so.name LIKE 'FOO\_%' ESCAPE '\'    
      AND sc1.text LIKE '% IN (%)'   ) 
BEGIN     
   SELECT     'ALTER VIEW dbo.' + so.name + 
      ' AS SELECT f.* FROM dbo.foo f, bar l ' +
      ' WHERE f.id = l.id ' +
      ' AND l.id = '     +  
       RIGHT(so.name, len(so.name) - charindex('_', so.name))    
            AS alterViewCommand     
   INTO #viewCorrections     
   FROM syscomments sc1     
   INNER JOIN sysobjects so ON so.id = sc1.id   
      WHERE so.type ='V'    
      AND so.name LIKE 'FOO\_%' ESCAPE '\'    
      AND sc1.text like '% IN (%)'     

   DECLARE @sql VARCHAR(4000)     

   WHILE EXISTS( SELECT 1 FROM #viewCorrections )    
   BEGIN
         SELECT TOP 1 @sql = alterViewCommand FROM #viewCorrections

         PRINT @sql

         EXEC ( @sql )

         DELETE FROM #viewCorrections WHERE alterViewCommand = @sql

       WAITFOR DELAY '000:00:05'
    END

    DROP TABLE #viewCorrections
END

OT: March Mdness 2011

RickHeiges — Mon, 14 Mar 2011 11:11:00 GMT

This past fall, I decided to take a break from Fantasy Football. Did I miss it? Yes to some extent. Fantasy Football can really eat up a lot of time.

But - I still love March Madness (NCAA Men's Basketball Tourney). It doesn't take much time to pick out teams. Since you can't make any changes after the deadline and the computer keeps track of scoring/scenarios/etc, it is a fun thing that really takes a little time and can help you enjoy the games a bit more. Let's see how good you are at picking winners with others within the SQL Community. The number of slots is unlimited. Here is the link...

http://tournament.fantasysports.yahoo.com/t1/register/joinprivategroup_assign_team?GID=62763&P=sqlblog

The password is "sqlblog". Fill out a bracket and compete for bragging rights!

Sudoku Solver

merrillaldrich — Sun, 18 Apr 2010 00:16:00 GMT

Today I am putting up something silly, just for fun. I set myself the task a while back to write a Sudoku solver in T-SQL, but with two dumb constraints that I would never follow given a real problem: I didn’t look at any documented techniques for solving Sudoku, and I specifically avoided T-SQL solutions, even though this has been done already many times. (The first thing I do with a real problem is to see who solved it already, and how, since most things have been done already. Not checking is a sure way to get inducted into The International Society of Wheel Re-inventors®.) So this solution is quite naive and probably has some gaps in it. I imagine it does the same thing as some other solvers, but, you’ll have to trust me, that’s a coincidence. Still, it gave me something to do evenings while my wife was doing … erm … Sudoku.

Anyway, the challenge I set for myself was to try to make a solver that:

Is completely set-based, in the spirit of both SQL and Sudoku.
Has as few statements as possible. I actually tried to write a single recursive CTE to solve a whole puzzle, but I didn’t quite get there, because I ran up against a limitation where you cannot reference a recursive member more than once in a CTE, and I’m not quite smart enough to solve that. I still have a hunch that it’s possible. The solution I do have consists of two statements with some flow control around them.
Should be reasonable to compute – that is, it’s not a brute-force method.

At a high level, the algorithm I came up with follows this logic:

The set of digits 1-9 is loaded into a numbers table “allValues.”
The set of all possible “cells” – all the boxes in the puzzle – is loaded into a second numbers-like table, “allCells.” This table just provides the address of each container / cell in the puzzle, to facilitate creating a left-join that will produce all the cells in a whole solution.
A puzzle is loaded into a third table, “puzzle,” which will start with the given values in the puzzle and ultimately hold the solution. This table is constrained with the same rules as the paper puzzle, so constraints enforce that it’s not possible to insert values into cells that break the rules of Sudoku.
A solver script is run against the tables:

While the puzzle is unsolved, repeat:

Compute the set of all possible values that can be inserted into all empty cells in the puzzle without breaking any rule
From that set, select any cells/values that are solvable because either there is only one possible value for the cell OR there is only one possible location for a given digit 0-9 in a row, column, or quadrant. That is, fill in cells that have deterministic solutions based on the existing values in the puzzle. (This usually is all that is required to solve an “easy” level puzzle, but won’t complete for a hard one.) Insert these deterministic values into the puzzle table.
IF there are no results from the prior step, that is, there are no solve-able cells, then:
1. Branch the solution by making a copy of it, so that there are two versions in the puzzle table. One ultimately will be correct, and one will be unsolvable.
2. Find one cell within the whole set of possible values that has two possible answers, and put one possibility into the first version, and the second possibility into the second version.
IF the insert of solved cells from step 2 failed, due to a constraint violation, then that implies that one of the branched versions of the puzzle in the table has reached an impasse: that is, it’s incorrect and unsolvable. Delete this version, leaving the correct one, and continue.

Setup

Designing the structure of the puzzle table was a little tricky. As we know, relational tables are not like actual grids because the order of both the rows and columns is undefined. All one can say about the values in a relation is that they are in the same row or in the same column, but there is no relative position as there is in a grid. So as tempting as it seems, we can’t represent the puzzle grid literally, shoving it into a table, because the positions of the cells in the paper grid carry meaning, while the positions of values in a relational table can’t. Basically, in SQL Server there is no “first” row or “first” column, and value cannot be said to be “next to” another value.

So, I arrived at a design that normalizes the data from the puzzle by creating a separate row for each cell in the whole puzzle, basically un-pivoting the grid of cells from the paper grid into a list. Each row in the resulting table stores an address for the position in the paper puzzle as Row, Column and Quadrant (the nine-square regions within the puzzle), with the digit in that cell as “Value.” The quadrant is obviously determined by the (row, column) pair and is deterministic, so that can be calculated using a computed column. The table definition looks like this:

CREATE TABLE dbo.Puzzle(
    SolutionID tinyint NOT NULL,
    Row tinyint NOT NULL,
    Col char(1) NOT NULL,
    Quadrant  AS (
        ('Q-' + 
        case when Row BETWEEN 1 AND 3 then 'A' 
        when Row BETWEEN 4 AND 6 then 'B' 
        when Row BETWEEN 7 AND 9 then 'C'  end )
        + case when Col BETWEEN 'A' AND 'C' then 'A' 
        when Col BETWEEN 'D' AND 'F' then 'B' 
        when Col BETWEEN 'G' AND 'I' then 'C'  end ),
    Value tinyint NOT NULL
)

Next, I added some rules to that table that make it mimic the “rules” implied by position in the paper version of the puzzle: no two cells in the same row, column, or quadrant can contain the same digit:

CREATE UNIQUE NONCLUSTERED INDEX ValsInaColumnAreUnique ON dbo.Puzzle 
(
    SolutionID ASC,
    Col ASC,
    Value ASC
)

CREATE UNIQUE NONCLUSTERED INDEX ValsInaRowAreUnique ON dbo.Puzzle 
(
    SolutionID ASC,
    Row ASC,
    Value ASC
)

CREATE UNIQUE NONCLUSTERED INDEX ValsInaQuadAreUnique ON dbo.Puzzle 
(
    SolutionID ASC,
    Quadrant ASC,
    Value ASC
)

ALTER TABLE dbo.Puzzle  WITH CHECK ADD  CONSTRAINT [ColIsA-I] CHECK  ( Col like '[A-I]' )

ALTER TABLE dbo.Puzzle CHECK CONSTRAINT [ColIsA-I]

ALTER TABLE dbo.Puzzle  WITH CHECK ADD  CONSTRAINT [RowIs1-9] CHECK  ( Row BETWEEN 1 AND 9 )

ALTER TABLE dbo.Puzzle CHECK CONSTRAINT [RowIs1-9]

ALTER TABLE dbo.Puzzle  WITH CHECK ADD  CONSTRAINT [ValueIs1-9] CHECK  ( Value BETWEEN 1 AND 9 )

ALTER TABLE dbo.Puzzle CHECK CONSTRAINT [ValueIs1-9]

The allCells table is similar, but without the need for a SolutionID or Values column – it’s just a list of all the cells in one puzzle grid. The computed column for Quadrant is the same:

CREATE TABLE dbo.allCells(
    Row tinyint NOT NULL,
    Col char(1) NOT NULL,
    Quadrant  AS (
        ('Q-' + 
        case when Row BETWEEN 1 AND 3 then 'A' 
        when Row BETWEEN 4 AND 6 then 'B' 
        when Row BETWEEN 7 AND 9 then 'C'  end )
        + case when Col BETWEEN 'A' AND 'C' then 'A' 
        when Col BETWEEN 'D' AND 'F' then 'B' 
        when Col BETWEEN 'G' AND 'I' then 'C'  end ),
)

INSERT dbo.allCells (Row, Col) VALUES (1, N'A')
INSERT dbo.allCells (Row, Col) VALUES (2, N'A')
INSERT dbo.allCells (Row, Col) VALUES (3, N'A')
INSERT dbo.allCells (Row, Col) VALUES (4, N'A')

…

INSERT dbo.allCells (Row, Col) VALUES (8, N'I')
INSERT dbo.allCells (Row, Col) VALUES (9, N'I')

Lastly, the numbers table:

CREATE TABLE dbo.allValues(
    Value int NOT NULL
)

INSERT dbo.allValues (Value) VALUES (1)
INSERT dbo.allValues (Value) VALUES (2)

…

INSERT dbo.allValues (Value) VALUES (9)

Loading a puzzle is a matter of running inserts against the Puzzle table to put in the given values, with SolutionID 0:

INSERT INTO dbo.Puzzle ( SolutionID, Row, Col, Value ) VALUES ( 0, 1, 'B', 3 )
INSERT INTO dbo.Puzzle ( SolutionID, Row, Col, Value ) VALUES ( 0, 1, 'I', 8 )
INSERT INTO dbo.Puzzle ( SolutionID, Row, Col, Value ) VALUES ( 0, 2, 'A', 2 )
INSERT INTO dbo.Puzzle ( SolutionID, Row, Col, Value ) VALUES ( 0, 2, 'B', 4 )
…

INSERT INTO dbo.Puzzle ( SolutionID, Row, Col, Value ) VALUES ( 0, 2, 'I', 6 )

Note that the Puzzle table doesn’t contain “empty” cells, only solved cells, and it cannot contain invalid values. It might, however, have an unsolvable puzzle even though each value present doesn’t violate the rules – a fact that will become important later.

Viewing a Puzzle

Next, it’s important (and more fun!) to be able to view the puzzle in a grid, as it looks on paper. I struggled with this a bit until realizing that this is basically a pivot problem, and the pivot operator can be used to rotate the puzzle table back into the grid:

SELECT [A], [B], [C], [D], [E], [F], [G], [H], [I]
FROM
( SELECT Puzzle.Value, allCells.Row, allCells.Col
    FROM dbo.allCells
    LEFT JOIN Puzzle on allCells.row = puzzle.Row and allCells.col = puzzle.col
    WHERE Puzzle.SolutionID = 0
) AS sourceTable PIVOT(
    min( Value ) for Col in ( [A], [B], [C], [D], [E], [F], [G], [H], [I] )
) AS PivotTable
ORDER BY Row

Only the non-null cells in the puzzle are present in the Puzzle table, but that set gets expanded via left-join to the allCells table to make a derived table with all 81 cells. That derived table is then pivoted on the columns to create nine columns by nine rows, and the resulting grid looks like the paper puzzle:

Sudoku Solver

At this point, we can check out the solver. The solver consists basically of two (evil, complicated) statements: one that can insert solved cells into the puzzle table, and a second that can detect and delete an unsolvable version of a puzzle. Those two statements are connected by flow control: a While loop that keeps the script going until the puzzle is solved, and a Try/Catch that handles the scenario where a version of a puzzle becomes unsolvable.

-- Loop while there is no solution having all 81 cells solved:
WHILE NOT EXISTS ( 
    SELECT SolutionID 
    FROM Puzzle 
    GROUP BY SolutionID 
    HAVING COUNT(*) = 81 
) BEGIN
    BEGIN TRY;
    -- Try to insert new solved cells into the puzzle table:
    
    WITH 

        -- Every possible new value, for every empty cell in every puzzle version, 
        -- that does not contradict the solved cells already present in the puzzle table:
        allPossibleNewValues
          AS ( SELECT   allSolutions.SolutionID ,
                        allCells.Row ,
                        allCells.Col ,
                        allCells.Quadrant ,
                        allValues.Value
               FROM     allValues
                        CROSS JOIN allCells
                        CROSS JOIN ( SELECT DISTINCT
                                            SolutionID
                                     FROM   dbo.Puzzle
                                   ) AS allSolutions
                        LEFT JOIN dbo.Puzzle ON allSolutions.SolutionID = Puzzle.SolutionID
                                             AND allCells.Row = Puzzle.Row
                                             AND allcells.Col = Puzzle.Col
               WHERE    -- The cell isn't already solved:
                        puzzle.Value IS NULL
                        
                        -- And there's no cell in the same row having the given value
                        AND NOT EXISTS ( SELECT *
                                         FROM   puzzle r
                                         WHERE  r.SolutionID = allSolutions.SolutionID
                                                AND r.Row = allcells.Row
                                                AND r.Value = allValues.Value )
                                                
                        -- And there's no cell in the same column having the given value                    
                        AND NOT EXISTS ( SELECT *
                                         FROM   puzzle c
                                         WHERE  c.SolutionID = allSolutions.SolutionID
                                                AND c.Col = allcells.Col
                                                AND c.Value = allValues.Value )
                                                
                        -- And there's no cell in the same quadrant having the given value
                        AND NOT EXISTS ( SELECT *
                                         FROM   puzzle q
                                         WHERE  q.SolutionID = allSolutions.SolutionID
                                                AND q.Quadrant = allCells.quadrant
                                                AND q.Value = allValues.Value )
             ),

        -- There are two sets that give us new solved cells to insert into the puzzle: 
        
        -- SureThings are values for empty cells, where the existing values already solved
        -- in the puzzle imply than only one value can go in the cell (there's literally only  
        -- one possibility for the unsolved cell, so it has to be correct):

        sureThings
          AS ( SELECT   SolutionID ,
                        Row ,
                        Col ,
                        MIN(Value) Value
               FROM     allPossibleNewValues
               GROUP BY SolutionID ,
                        Row ,
                        Col ,
                        Quadrant
               HAVING   COUNT(*) = 1
             ),

        -- ForcedDigits are values determined by process of elimination: each digit 1-9 has
        -- to find a "home" in every row, every column and every quadrant. That means that
        -- if a value appears only one time in the set of all possible values for any row, 
        -- column or quadrant, then it has to be the solution for that cell:
     
        forcedDigits
          AS ( SELECT   SolutionID ,
                        Row ,
                        Col ,
                        Value
               FROM     allPossibleNewValues n
               WHERE    
            
            -- There is no other location in the same row that can have the given value
            -- IOW, the given value must go in a cell, because it cannot go anyplace else
            
                        NOT EXISTS ( SELECT *
                                     FROM   ( SELECT    SolutionID ,
                                                        Row ,
                                                        Col ,
                                                        Value
                                              FROM      allPossibleNewValues rows1
                                              UNION ALL
                                              SELECT    SolutionID ,
                                                        Row ,
                                                        Col ,
                                                        Value
                                              FROM      dbo.Puzzle rows2
                                            ) AS [rows]
                                     WHERE  [rows].SolutionID = n.SolutionID
                                            AND [rows].Row = n.Row
                                            AND [rows].Col != n.Col
                                            AND [rows].Value = n.Value )
                        OR

            -- There is no other location in the same column where the given value can go
            
                        NOT EXISTS ( SELECT *
                                     FROM   ( SELECT    SolutionID ,
                                                        Row ,
                                                        Col ,
                                                        Value
                                              FROM      allPossibleNewValues cols1
                                              UNION ALL
                                              SELECT    SolutionID ,
                                                        Row ,
                                                        Col ,
                                                        Value
                                              FROM      dbo.Puzzle cols2
                                            ) AS [cols]
                                     WHERE  [cols].SolutionID = n.SolutionID
                                            AND [cols].Row != n.Row
                                            AND [cols].Col = n.Col
                                            AND [cols].Value = n.Value )
                        OR
            
            -- There is no other cell in the same quadrant where the given value can go
            
                        NOT EXISTS ( SELECT *
                                     FROM   ( SELECT    SolutionID ,
                                                        Row ,
                                                        Col ,
                                                        Quadrant ,
                                                        Value
                                              FROM      allPossibleNewValues quads1
                                              UNION ALL
                                              SELECT    SolutionID ,
                                                        Row ,
                                                        Col ,
                                                        Quadrant ,
                                                        Value
                                              FROM      dbo.Puzzle quads2
                                            ) AS [quads]
                                     WHERE  [quads].SolutionID = n.SolutionID
                                            AND [quads].quadrant = n.quadrant
                                            AND ( [quads].Col != n.Col
                                                  OR [quads].Row != n.Row
                                                )
                                            AND [quads].Value = n.Value )
             )
                
        INSERT  INTO Puzzle
                ( SolutionID ,
                  Row ,
                  Col ,
                  Value 
                )
                
        -- New solved cells, if there are any
        SELECT SolutionID ,
                Row ,
                Col ,
                Value 
         FROM (
                SELECT  SolutionID ,
                        Row ,
                        Col ,
                        Value
                FROM    sureThings
                UNION
                SELECT  SolutionID ,
                        Row ,
                        Col ,
                        Value
                FROM    forcedDigits
        ) as solutions
        
        UNION
        
        -- Otherwise, branch by duplicating the existing solution as (solutionid + 1) plus
        -- insert one trial cell value into the existing solution, and another trial value 
        -- into the new solution:

        SELECT SolutionID ,
            Row ,
            Col ,
            Value
        FROM (
            -- A copy of the existing version of the puzzle:
            SELECT ( SELECT MAX( SolutionID ) from dbo.Puzzle ) + 1 as SolutionID,
                Row ,
                Col ,
                Value
            FROM dbo.Puzzle
            
            UNION
            
            -- One each of two possible values for a cell - one directed to the existing
            -- solution and one to the copy, by Row_Number():
            SELECT ( SELECT MIN( SolutionID ) FROM dbo.Puzzle ) 
                + ( ROW_NUMBER() OVER ( ORDER BY split.Row, split.Col ) - 1 ) as SolutionID ,
                split.Row ,
                split.Col ,
                split.Value
            FROM allPossibleNewValues split
                INNER JOIN ( 
                    SELECT TOP ( 1 ) Row, Col 
                    FROM allPossibleNewValues 
                    GROUP BY Row, Col
                    HAVING COUNT(*) = 2
                    ORDER BY Row, Col 
                ) as firstPair on split.Row = firstPair.Row 
                    and split.Col = firstPair.Col
                    
        ) AS copyPuzzle
        
        -- Only in cases where there were no new solved cells 
        -- in sureThings or forcedDigits
        WHERE ( SELECT COUNT(*) FROM sureThings ) = 0 
            and ( SELECT COUNT(*) FROM forcedDigits ) = 0;

    END TRY

    BEGIN CATCH;
    -- If the insert above failed due to constraint violation, that means that
    -- one version of the puzzle is contradictory/unsolvable.
    -- Find and delete the solution at an impasse:
    
    WITH 

        -- Every possible new value, for every empty cell, that does not contradict the
        -- solved cells already present in the puzzle (same logic as above):

        allPossibleNewValues
          AS ( SELECT   allSolutions.SolutionID ,
                        allCells.Row ,
                        allCells.Col ,
                        allCells.Quadrant ,
                        allValues.Value
               FROM     allValues
                        CROSS JOIN allCells
                        CROSS JOIN ( SELECT DISTINCT
                                            SolutionID
                                     FROM   dbo.Puzzle
                                   ) AS allSolutions
                        LEFT JOIN dbo.Puzzle ON allSolutions.SolutionID = Puzzle.SolutionID
                                             AND allCells.Row = Puzzle.Row
                                             AND allcells.Col = Puzzle.Col
               WHERE    -- The cell isn't already solved:
                        puzzle.Value IS NULL
                        
                        -- And there's no cell in the same row having the given value
                        AND NOT EXISTS ( SELECT *
                                         FROM   puzzle r
                                         WHERE  r.SolutionID = allSolutions.SolutionID
                                                AND r.Row = allcells.Row
                                                AND r.Value = allValues.Value )
                                                
                        -- And there's no cell in the same column having the given value                    
                        AND NOT EXISTS ( SELECT *
                                         FROM   puzzle c
                                         WHERE  c.SolutionID = allSolutions.SolutionID
                                                AND c.Col = allcells.Col
                                                AND c.Value = allValues.Value )
                                                
                        -- And there's no cell in the same quadrant having the given value
                        AND NOT EXISTS ( SELECT *
                                         FROM   puzzle q
                                         WHERE  q.SolutionID = allSolutions.SolutionID
                                                AND q.Quadrant = allCells.quadrant
                                                AND q.Value = allValues.Value )
             ),


        -- ForcedDigits are values determined by process of elimination: each digit 1-9 has
        -- to find a "home" in every row (same logic as above):
     
        forcedDigits
          AS ( SELECT   SolutionID ,
                        Row ,
                        Col ,
                        Quadrant ,
                        Value
               FROM     allPossibleNewValues n
               WHERE    
            
            -- There is no other location in the same row that can have the given value
            -- IOW, the given value must go in a cell, because it cannot go anyplace else
            
                        NOT EXISTS ( SELECT *
                                     FROM   ( SELECT    SolutionID ,
                                                        Row ,
                                                        Col ,
                                                        Value
                                              FROM      allPossibleNewValues rows1
                                              UNION ALL
                                              SELECT    SolutionID ,
                                                        Row ,
                                                        Col ,
                                                        Value
                                              FROM      dbo.Puzzle rows2
                                            ) AS [rows]
                                     WHERE  [rows].SolutionID = n.SolutionID
                                            AND [rows].Row = n.Row
                                            AND [rows].Col != n.Col
                                            AND [rows].Value = n.Value )
                        OR

            -- There is no other location in the same column where the given value can go
            
                        NOT EXISTS ( SELECT *
                                     FROM   ( SELECT    SolutionID ,
                                                        Row ,
                                                        Col ,
                                                        Value
                                              FROM      allPossibleNewValues cols1
                                              UNION ALL
                                              SELECT    SolutionID ,
                                                        Row ,
                                                        Col ,
                                                        Value
                                              FROM      dbo.Puzzle cols2
                                            ) AS [cols]
                                     WHERE  [cols].SolutionID = n.SolutionID
                                            AND [cols].Row != n.Row
                                            AND [cols].Col = n.Col
                                            AND [cols].Value = n.Value )
                        OR
            
            -- There is no other cell in the same quadrant where the given value can go
            
                        NOT EXISTS ( SELECT *
                                     FROM   ( SELECT    SolutionID ,
                                                        Row ,
                                                        Col ,
                                                        Quadrant ,
                                                        Value
                                              FROM      allPossibleNewValues quads1
                                              UNION ALL
                                              SELECT    SolutionID ,
                                                        Row ,
                                                        Col ,
                                                        Quadrant ,
                                                        Value
                                              FROM      dbo.Puzzle quads2
                                            ) AS [quads]
                                     WHERE  [quads].SolutionID = n.SolutionID
                                            AND [quads].quadrant = n.quadrant
                                            AND ( [quads].Col != n.Col
                                                  OR [quads].Row != n.Row
                                                )
                                            AND [quads].Value = n.Value )
             )
                DELETE dbo.Puzzle 
                
                -- An unsolvable puzzle version at an impasse will have an impossible 
                -- result for forcedDigits. That is, two values forced into one cell,
                -- or same values forced into the same row, column, or quadrant. Find
                -- the unsolvable version of the puzzle to delete:
                WHERE SolutionID = (
                    SELECT TOP ( 1 ) SolutionID FROM (
                        SELECT SolutionID, Row, Col 
                        FROM forcedDigits
                        GROUP BY SolutionID, Row, Col
                        HAVING COUNT(*) > 1 ) as impasse1
                    )
                OR SolutionID = (
                    SELECT TOP ( 1 ) SolutionID FROM (
                        SELECT SolutionID, Row, Value 
                        FROM forcedDigits 
                        GROUP BY SolutionID, Row, Value
                        HAVING COUNT(*) > 1 ) AS impasse2
                    )
                OR SolutionID = (
                    SELECT TOP ( 1 ) SolutionID FROM (
                        SELECT SolutionID, Col, Value 
                        FROM forcedDigits 
                        GROUP BY SolutionID, Col, Value
                        HAVING COUNT(*) > 1 ) as impasse3
                    )
                OR SolutionID = (
                    SELECT TOP ( 1 ) SolutionID FROM (
                        SELECT SolutionID, Quadrant, Value 
                        FROM forcedDigits 
                        GROUP BY SolutionID, Quadrant, Value
                        HAVING COUNT(*) > 1 ) AS impasse4
                    );
    END CATCH;
END;

So far this has solved each puzzle I’ve fed into it. If I were a mathematician, I suppose I would be able to prove whether it can really solve any puzzle or not, but, alas, I am not that smart. Let me know what you think, or if you’ve tried this before what your approach was. And if anyone has the recursive, one-statement version I’d love to see it!

I’m attaching a ZIP with all the code for this solution. If you want to try it out:

Make a database called Sudoku
Run the DB Create.sql script to make the tables
Run one of the provided sample puzzle scripts to load a puzzle (one is an “easy” puzzle, one is an “evil” puzzle)
Run the Viewer.sql script to view the loaded puzzle
Run Solver.sql to solve the puzzle
Run Viewer.sql (perhaps changing the value of SolutionID) to view the solved puzzle

OT: NCAA Pick'em Returns...

RickHeiges — Sun, 14 Mar 2010 19:28:00 GMT

Every year in March, the Men's College Basketball Championship Tourney Begins. For the past few years, I've put together a "League". This year is no different. The prize... Bragging Rights - that's it - nothing else....

Follow the link below to sign up! Picks must be made by Thursday before the games begin.

http://tournament.fantasysports.yahoo.com/t1/register/joinprivategroup_assign_team?GID=65521&P=sqlblog&P=sqlblog

SQL Saturday #33 in Charlotte!

RickHeiges — Fri, 05 Feb 2010 16:35:00 GMT

SQL Saturday is coming to Charlotte next month! If you are in the area, come on by. We have a great line-up of speakers. Find out more information at http://www.sqlsaturday.com/33/eventhome.aspx