The Sodoku Puzzle:
I have to assume that you know what a Sudoku puzzle is. If you have been on Mars for a few years, then go to Wikipedia and catch up. http://en.wikipedia.org/wiki/Sudoku Also, lose that pair of hip hugger bell bottom pants.

This is a single query Sudoku solver by Richard Romley in SQL Server dialect. If you are a long time fan, you will know that name from my columns in RDBMS and DATABASE PROGRAMMING & DESIGN magazines. Richard is now retired from Smith-Barney Solomon but when he was working on Wall Street, he was the "go to" SQL guy. On a regular basis, he cooked my SQL puzzles (note: 'to cook" is a verb in recreational mathematics that means to post a better solution than the person who posted the puzzle).

The purpose of this query is to take a 9x9 Sudoku grid as input and return ALL -- repeat ALL -- possible solution grids. I bet you thought that a puzzle always had a single solution. Nope. In fact, Richard found one published puzzle with over 35 answers.

The number of essentially different solutions, when symmetries such as rotation, reflection and re-labeling are taken into account, was shown by Ed Russell and Frazer Jarvis to be just 5,472,730,538 which is still a large result set.

There is an article on Sodoku solving from IEEE SPECTRUM on-line about how it is NP-complete. There is a proof that if you have 26 known cells at the start, then you have one and only one answer. Less than that, you cannot predict the size of the answer set. If you want to do something very dumb with this code, then type in the digits one to nine in a single row or column. You can then bitch that it failed to return hundreds of millions of answer girds in less than a second! Yes, someone actually did this!

The real purpose of the procedure is to demonstrate that:

1) A long parameter list is not harmful. So instead of writing a parser in a proprietary 3GL language, XML or whatever, you can depend on the compiler to do all that checking and validation. Considering that most proprietary solutions do not bother with all that checking and validation of input like a compiler, it is not a fair comparison. If the answer does not have to be right, the answer is always 42.

2) A huge multi-table self-join (i.e. 81 correlations) is not harmful when the tables are small. Avoiding self-joins was a heuristic a few years ago, but the optimizers are smarter, primary storage is bigger and it just might be time to re-think things.

The code is posted here.

Parking Lot Problem:
One of the classic questions Newbies ask is how to "fill in the holes" in a columns with sequential numbers. This is usually because they are trying to imitate a fixed length record sequential file system in SQL and want to use this column as a physical position/primary key. Imagine that you have a row of automobiles in a parking lot with numbered spaces, and every time a new car parks, you want to identify it by the number of the parking space that it got this time. And if an old car comes back, you want to change its primary key to the lowest numbered empty space. 

Yes, I know that it's "dumber than dirt", but a lot of newbies do things like this. What you really wanted was the VIN (Vehicle Identification Number)on each car and a constraint to verify that it has the right syntax as described in the ISO 3779 standard. I'll get that at the end of this article. Just ignore what a bad idea this and assume we have a table like this:

CREATE TABLE ParkingLot
(space_nbr INTEGER NOT NULL PRIMARY KEY
CHECK(space_nbr BETWEEN 1 AND {{upper limit}},
<< other stuff >>);

If you have used the common SQL programming trick of keeping an auxiliary table with a list of sequential numbers from 1 to {{upper limit}} in your schema and you are using a product with full SQL-92 and the lower range boundary is one, then you can solve the problem with this query:

SELECT MIN (X.space_nbr)
FROM (SELECT space_nbr FROM ParkingLot) 
EXCEPT
SELECT seq
FROM Sequence
WHERE seq <= {{upper limit}})
AS X(space_nbr);

The EXCEPT operator is the set subtraction and it appears in ORACLE as MINUS. While the EXCEPT operator is part of SQL-92, it is not implemented in most products, so you can use a NOT IN () predicate instead. 

If we treat a missing space_nbr of one as a special case, we came up with this answer: 

SELECT MIN(X.space_nbr)
FROM (SELECT CASE
WHEN 1 NOT IN (SELECT space_nbr FROM ParkingLot)
THEN 1
THEN (space_nbr + 1)
NOT IN (SELECT space_nbr FROM ParkingLot)
AND (space_nbr + 1) <= {{upper limit}})
THEN (space_nbr + 1)
ELSE NULL END
FROM ParkingLot) AS X(space_nbr);

The reason for using a derived table in the FROM clause is that you cannot put a subquery expression in an aggregate function like MIN(). This answer has the advantage of returning a NULL when the table is full, thus giving the user a clear message that the parking lot is full. 
The order of execution of the WHEN is important; it forces a front to back scan of the table.

NOTES ON VIN:
In North America, a system is used that is far more stringent than the ISO Standards but is "backward compatible." Here, the VIN is divided into four sections: 

The first three characters shall uniquely identify the manufacturer, make and type of vehicle (with the same exception of manufacturers that produce less than 500 vehicles). Effectively, this is the WMI. There are indeed examples of manufacturers who have more than one WMI that use the third character as a code for a vehicle category (for instance bus or truck). Just as often however this is not the case; 

The second section consists of five characters (VIN positions 4-8) and identifies the attributes of the vehicle. For each type of vehicle (passenger cars, MPV's, trucks, buses, trailers, motorcycles, incomplete vehicles other than trailers), different information is required. For cars, MPV's and light trucks it is required that the first two characters of this section are alphabetic, the third and fourth shall be numeric and the fifth alphanumeric. This section is the VDS in ISO 3779 but there it comprises another position of the VIN; 

The third section consists of one character which is the check digit, calculated over the other 16 characters of the VIN. This character can be numeric or the letter X; 
The fourth section consists of eight characters on positions 10-17 of the VIN. The last five shall be numeric for cars, MPV's and light trucks and the last four shall be numeric for all other vehicles. The first character represents the vehicle model year, the second character represents the plant of manufacture. The third through eighth characters are a sequential production number (for manufacturers producing more than 500 vehicles per year). For other manufacturers, the sixth, seventh and eight positions represent the sequential production number. 

This section confirms to the VIS in ISO 3779. 

A portion of the VIN is the WMI (World Manufacturer Identifier) Code. SAE assigns this code to U.S. vehicle manufacturers. If you are a U.S. manufacturer, please contact: 

Cathy Douds
WMI Coordinator
SAE International
400 Commonwealth Drive
Warrendale, PA 15096-0001
724.772.8511
724.776.4026 - fax
douds@sae.org 

Related Standards:

There are several standards available on VINs and WMIs: 

SAE - J187 - Truck Vehicle Identification Numbers
SAE - J218 - Passenger Car Identification Terminology
SAE - J272 - Vehicle Identification Number Systems
SAE - J273 - Passenger Car Vehicle Identification Number System
SAE - J853 - Vehicle Identification Numbers
SAE - J1108 - Truck and Truck Tractor Vehicle Identification Number Systems
SAE - J1044 - World Manufacturer Identifier
SAE - J1229 - Truck Identification Terminology
SAE - J1877 - Recommended Practice for Bar-Coded Vehicle Identification Number Label


SAE J129 - Engine and Transmission Identification Numbers
ISO 3779 - Road vehicles - Vehicle identification number (VIN) Content and structure
ISO 3780 - Road vehicles - World manufacturer identifier (WMI) code