Using SQL Server to solve Einstein’s puzzles

A particular category of logic puzzles have to do with the satisfaction of constraints. Among those are the so called “Einstein’s puzzles”, also called “zebra puzzles“. The first time I saw such a puzzle was about 10 years ago. I immediately thought that such puzzles could be solved using SQL Server.

Indeed, I thought that it would be easy to use a SELECT statement without a WHERE clause to get the Cartesian product from tables that would list all the entities involved. This SELECT statement would populate a “main table” that would keep all possibilities. Then, we would translate each constraint to DELETE statements that would eliminate from the main table the rows that do not fit the particular constraint. When all constraints would have been accounted for, in the main table there would remain only the rows that correspond to the solution of the puzzle.

The problem I faced early on was that most Einstein puzzles have some constraints that are difficult to “translate” to straightforward DELETE statements. Instead, these constraints can be handled by writing very specific programs that examine the rows of the main table and perform deletions based on the particular rules of the constraint statement.

Again, in order to make Einstein puzzles more challenging, their creators devise most constraints in a way that makes it impossible to “translate” them to simple and straightforward DELETE statements from a main table that contains all possibilities. Even the original (i.e. the first) Einstein puzzle exhibits this practice.

In order to provide a proof-of-concept solution to such a puzzle, I needed a puzzle that provided straightforward constraints. The existence of complex constraints that cannot be represented by DELETE statements (and instead need specific programming) would complicate my analysis and would obscure its main points.

Thus, for this analysis, I chose to create my own puzzle (based on a “story” and on “entities” from my own imagination). Of course, the story and the entities are not what is important here; what is important are the constraints that I will choose to introduce. All the constraints that I will introduce in this puzzle lack complexity and “translate” to straightforward DELETE statements. I believe that this practice will help showcase the concepts that are needed in order to understand how a relational database like SQL Server can be used to solve these kind of puzzles.

The puzzle I devised is the following:

In an airport, five different couples showed up. Each couple was heading to a different destination. Each couple also had a suitcase with them. Each suitcase had a different color and a different dangerous item within. Your mission, should you decide to accept it, is to find the exact details: For each couple, you have to find the husband, the wife, their destination, the color of their suitcase and the dangerous item within the suitcase.

The names of the husbands in alphabetical order are: Adam, Bill, Chad, Dave, Eric. The names of the wives in alphabetical order are: Annabell, Beatrice, Christin, Dorothea, Elleonor. The destinations in alphabetical order are: China, France, Greece, Italy, Japan. The colors of the suitcases in alphabetical order are: Blue, Green, Red, White, Yellow. The dangerous items in alphabetical order are: Cutter, Hammer, Knife, Pistol, Wrench.

I will go ahead and give you the solution that I prearranged. The constraints that I will provide will come straight from this solution.

Adam Dorothea Greece Green  Cutter
Bill Elleonor Japan  Red    Wrench
Chad Christin Italy  Yellow Hammer
Dave Annabell China  White  Pistol
Eric Beatrice France Blue   Knife

After I arranged the solution, I wrote a SQL script that creates a database. In that database, it creates one table that lists the husbands, one that lists the wives and so on. It then uses a SELECT statement FROM those tables without a WHERE clause. In effect, this produces the Cartesian product of the available combinations/possibilities. The rows from the SELECT statement populate the main table. Then, I devise constraints. I am careful when I create the constraints, so that each constraint is not redundant. I check that each constraint leads to the elimination of rows from  the main table. Here are the constraints I came up with:

01. The couple that headed to Italy had a hammer in their suitcase.
02. Elleonor and her husband were going to Japan.
03. There was a pistol in the white suitcase.
04. Eric and Beatrice are married to each other.
05. Adam and his wife carried a green suitcase.
06. Bill and his wife had a wrench in their suitcase.
07. The couple that was going to Greece had a green suitcase.
08. Annabell and her husband were heading to China.
09. The red suitcase contained a wrench.
10. Chad and Christin are married.
11. Beatrice and her husband were carrying a knife in their suitcase.
12. Chad and his wife carried a yellow suitcase.
13. Dave and Annabell are married.
14. The cutter was in the green suitcase.
15. Dorothea and her husband were not going to France.

For each constraint I devised, I created corresponding DELETE statements that enforced those constraints, by eliminating the rows that did not apply. I kept adding constraints until only 5 rows remained. The 5 rows that remained are the solution rows that I just presented above. It took me 15 simple constraint statements to eliminate all invalid rows.

The SQL script that I wrote is presented below. I run it using a Microsoft SQL Server 2005 Express instance that I happened to have in my PC for another reason. After each constraint is applied, I provide the row count of the main table. This way, we can see the row count diminishing after each constraint is acknowledged.

PRINT 'In an airport, five different couples showed up.'
PRINT 'Each couple was heading to a different destination.'
PRINT 'Each couple also had a suitcase with them.'
PRINT 'Each suitcase had a different color and a different dangerous item within.'
PRINT 'Your mission, should you decide to accept it, is to find the exact details:'
PRINT 'For each couple, you have to find the husband, the wife, their destination,'
PRINT 'the color of their suitcase and the dangerous item within the suitcase.'

USE master
GO

CREATE DATABASE PuzzleDatabase
GO

USE PuzzleDatabase
GO

CREATE TABLE PuzzleTable
(
   Husband     VARCHAR(10),
   Wife        VARCHAR(10),
   Destination VARCHAR(10),
   Color       VARCHAR(10),
   Item        VARCHAR(10)
)
GO

CREATE TABLE HusbandTable     (HusbandColumn     VARCHAR(10))
GO
CREATE TABLE WifeTable        (WifeColumn        VARCHAR(10))
GO
CREATE TABLE DestinationTable (DestinationColumn VARCHAR(10))
GO
CREATE TABLE ColorTable       (ColorColumn       VARCHAR(10))
GO
CREATE TABLE ItemTable        (ItemColumn        VARCHAR(10))
GO

PRINT ''
PRINT 'The names of the husbands in alphabetical order are:'
PRINT 'Adam, Bill, Chad, Dave, Eric.'

INSERT INTO HusbandTable (HusbandColumn) VALUES ('Adam')
GO
INSERT INTO HusbandTable (HusbandColumn) VALUES ('Bill')
GO
INSERT INTO HusbandTable (HusbandColumn) VALUES ('Chad')
GO
INSERT INTO HusbandTable (HusbandColumn) VALUES ('Dave')
GO
INSERT INTO HusbandTable (HusbandColumn) VALUES ('Eric')
GO

PRINT ''
PRINT 'The names of the wives in alphabetical order are:'
PRINT 'Annabell, Beatrice, Christin, Dorothea, Elleonor.'

INSERT INTO WifeTable (WifeColumn) VALUES ('Annabell')
GO
INSERT INTO WifeTable (WifeColumn) VALUES ('Beatrice')
GO
INSERT INTO WifeTable (WifeColumn) VALUES ('Christin')
GO
INSERT INTO WifeTable (WifeColumn) VALUES ('Dorothea')
GO
INSERT INTO WifeTable (WifeColumn) VALUES ('Elleonor')
GO

PRINT ''
PRINT 'The destinations in alphabetical order are:'
PRINT 'China, France, Greece, Italy, Japan.'

INSERT INTO DestinationTable (DestinationColumn) VALUES ('China')
GO
INSERT INTO DestinationTable (DestinationColumn) VALUES ('France')
GO
INSERT INTO DestinationTable (DestinationColumn) VALUES ('Greece')
GO
INSERT INTO DestinationTable (DestinationColumn) VALUES ('Italy')
GO
INSERT INTO DestinationTable (DestinationColumn) VALUES ('Japan')
GO

PRINT ''
PRINT 'The colors of the suitcases in alphabetical order are:'
PRINT 'Blue, Green, Red, White, Yellow.'

INSERT INTO ColorTable (ColorColumn) VALUES ('Blue')
GO
INSERT INTO ColorTable (ColorColumn) VALUES ('Green')
GO
INSERT INTO ColorTable (ColorColumn) VALUES ('Red')
GO
INSERT INTO ColorTable (ColorColumn) VALUES ('White')
GO
INSERT INTO ColorTable (ColorColumn) VALUES ('Yellow')
GO

PRINT ''
PRINT 'The dangerous items in alphabetical order are:'
PRINT 'Cutter, Hammer, Knife, Pistol, Wrench.'

INSERT INTO ItemTable (ItemColumn) VALUES ('Cutter')
GO
INSERT INTO ItemTable (ItemColumn) VALUES ('Hammer')
GO
INSERT INTO ItemTable (ItemColumn) VALUES ('Knife')
GO
INSERT INTO ItemTable (ItemColumn) VALUES ('Pistol')
GO
INSERT INTO ItemTable (ItemColumn) VALUES ('Wrench')
GO

PRINT ''
PRINT 'The following step is the most important one.'
PRINT 'We calculate all posibilities (i.e. the Cartesian product).'
PRINT '(5 husbands) x (5 wives) x (5 destinations) x (5 suitcase colors) x (5 dangerours items) ='
PRINT '= 5^5 possibilities = 3125 possibilities = 3125 rows.'
PRINT 'The SELECT statement does this calculation automatically for us,'
PRINT 'if we do not specify a WHERE clause.'

INSERT INTO PuzzleTable (Husband, Wife, Destination, Color, Item)
SELECT HusbandColumn, WifeColumn, DestinationColumn, ColorColumn, ItemColumn
FROM HusbandTable, WifeTable, DestinationTable, ColorTable, ItemTable
GO

PRINT ''
PRINT 'By monitoring the row count, we will be able to see'
PRINT 'how each restriction diminishes the number of rows/possibilities.'
PRINT 'When all of the restrictions have been acknowledged,'
PRINT 'only 5 rows should remain on the table.'
PRINT 'These 5 rows should correspond to the solution.'

SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '01. The couple that headed to Italy had a hammer in their suitcase.'

DELETE FROM PuzzleTable
WHERE Destination = 'Italy' AND Item != 'Hammer'
GO
DELETE FROM PuzzleTable
WHERE Destination != 'Italy' AND Item = 'Hammer'
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '02. Elleonor and her husband were going to Japan.'

DELETE FROM PuzzleTable
WHERE Wife = 'Elleonor' AND Destination != 'Japan'
GO
DELETE FROM PuzzleTable
WHERE Wife != 'Elleonor' AND Destination = 'Japan'
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '03. There was a pistol in the white suitcase.'

DELETE FROM PuzzleTable
WHERE Color = 'White' AND Item != 'Pistol'
GO
DELETE FROM PuzzleTable
WHERE Color != 'White' AND Item = 'Pistol'
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '04. Eric and Beatrice are married to each other.'

DELETE FROM PuzzleTable
WHERE Husband = 'Eric' AND Wife != 'Beatrice'
GO
DELETE FROM PuzzleTable
WHERE Husband != 'Eric' AND Wife = 'Beatrice'
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '05. Adam and his wife carried a green suitcase.'

DELETE FROM PuzzleTable
WHERE Husband = 'Adam' AND Color != 'Green'
GO
DELETE FROM PuzzleTable
WHERE Husband != 'Adam' AND Color = 'Green'
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '06. Bill and his wife had a wrench in their suitcase.'

DELETE FROM PuzzleTable
WHERE Husband = 'Bill' AND Item != 'Wrench'
GO
DELETE FROM PuzzleTable
WHERE Husband != 'Bill' AND Item = 'Wrench'
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '07. The couple that was going to Greece had a green suitcase.'

DELETE FROM PuzzleTable
WHERE Destination = 'Greece' AND Color != 'Green'
GO
DELETE FROM PuzzleTable
WHERE Destination != 'Greece' AND Color = 'Green'
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '08. Annabell and her husband were heading to China.'

DELETE FROM PuzzleTable
WHERE Wife = 'Annabell' AND Destination != 'China'
GO
DELETE FROM PuzzleTable
WHERE Wife != 'Annabell' AND Destination = 'China'
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '09. The red suitcase contained a wrench.'

DELETE FROM PuzzleTable
WHERE Color = 'Red' AND Item != 'Wrench'
GO
DELETE FROM PuzzleTable
WHERE Color != 'Red' AND Item = 'Wrench'
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '10. Chad and Christin are married.'

DELETE FROM PuzzleTable
WHERE Husband = 'Chad' AND Wife != 'Christin'  
GO
DELETE FROM PuzzleTable
WHERE Husband != 'Chad' AND Wife = 'Christin'
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '11. Beatrice and her husband were carrying a knife in their suitcase.'

DELETE FROM PuzzleTable
WHERE Wife = 'Beatrice' AND Item != 'Knife'
GO
DELETE FROM PuzzleTable
WHERE Wife != 'Beatrice' AND Item = 'Knife'
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '12. Chad and his wife carried a yellow suitcase.'

DELETE FROM PuzzleTable
WHERE Husband = 'Chad' and Color != 'Yellow'
GO
DELETE FROM PuzzleTable
WHERE Husband != 'Chad' and Color = 'Yellow'
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '13. Dave and Annabell are married.'

DELETE FROM PuzzleTable
WHERE Husband = 'Dave' and Wife != 'Annabell'
GO
DELETE FROM PuzzleTable
WHERE Husband != 'Dave' and Wife = 'Annabell'
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '14. The cutter was in the green suitcase.'

DELETE FROM PuzzleTable
WHERE Color = 'Green' and Item != 'Cutter'
GO
DELETE FROM PuzzleTable
WHERE Color != 'Green' and Item = 'Cutter'
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '15. Dorothea and her husband were not going to France.'

DELETE FROM PuzzleTable
WHERE Wife = 'Dorothea' and Destination = 'France'
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT 'The 5 rows that should remain on the table,'
PRINT 'i.e. the solution, should be:'
PRINT '----------------------------------'
PRINT 'Adam Dorothea Greece Green  Cutter'
PRINT 'Bill Elleonor Japan  Red    Wrench'  
PRINT 'Chad Christin Italy  Yellow Hammer'
PRINT 'Dave Annabell China  White  Pistol'
PRINT 'Eric Beatrice France Blue   Knife'
PRINT '----------------------------------'

SELECT * FROM PuzzleTable
GO

USE master
GO

DROP DATABASE PuzzleDatabase
GO

Here is the results tab after running the previous script:

SQL1

Although we eliminated all invalid rows, leaving only the 5 correct ones, it took us as much as 15 simple constraint statements to do that. Now, that may not be a problem in and of itself. What is a problem is that some of these constraints are redundant. We could have reached the solution using less constraints. To understand why, we have to realize that relying only on the DELETE statements is not enough. We have to be more thorough.

Translating a constraint statement to DELETE statements is not enough. After a deletion, we also have to check for the formation of unique relationships and use them to further eliminate invalid rows. Let me give you an example.

Suppose that we delete some rows. Then, checking the remaining rows, we observe that Adam only has Dorothea as his wife. There are no rows with Adam and another of the wives. Thus, we understand that Adam and Dorothea are a couple. This is great. And we owe it to the DELETE statements that we have been able to reach this conclusion. But as we continue to observe other rows, we find that other husbands have wives with Dorothea being one of them. For example, there are rows that list Bill with Dorothea, as well as with other wives as well. The same may happen, say, for Eric.

But, since we know that Adam and Dorothea are a couple, we can DELETE the rows that corresponds to Dorothea with other husbands.

The same goes for any combination of two different entitles. If, for example, we find that the rows containing the Destination Italy only have the Item Hammer and no other Items, then we immediately know that we should eliminate all rows that correspond to other destinations and hammers.

Thus, to extract the maximum information and to do the maximum elimination possible from the constraints, after the straightforward deletion statements, we should search for unique relationships and use them to further eliminate invalid rows.

In order to do that, I created a lengthy procedure that I call after each constraint has been acknowledged and handled. This procedure checks each and every pair of different entities, in order to find a unique correspondence. If it finds such a correspondence, it “propagates” this information, meaning that deletes the rows that are invalid due to this unique correspondence.

The procedure that checks each and every pair of different entities for a unique correspondence, also keeps track of whether it made any deletions or not. If it indeed made any deletions, it runs again, because there might be new unique correspondences that came up because of the deletions. And it continues to run again, as long as it makes any deletions in its previous run.

This procedure is lengthy (code-wise). It is a shame that I created it using such a verbose technique, especially when SQL Server scripts can be very versatile and dynamic. Programming a SQL Server script allows you to use dynamic SQL statements, thus forming your code on the fly. Still, I concentrated on the main concepts. Creating an elaborate, dynamic statement generation would have obscure the main points of this analysis.

Calling this procedure after each constraint has been handled, helps in the reduction of the constraints needed. Indeed, when we run the SQL script, we see that we reach the solution with no need for the last two constraints.

The SQL script, that contains the procedure that accounts for unique correspondences, and thus, “converges” faster (“faster” meaning “using less constraints”), is listed below:

PRINT 'In an airport, five different couples showed up.'
PRINT 'Each couple was heading to a different destination.'
PRINT 'Each couple also had a suitcase with them.'
PRINT 'Each suitcase had a different color and a different dangerous item within.'
PRINT 'Your mission, should you decide to accept it, is to find the exact details:'
PRINT 'For each couple, you have to find the husband, the wife, their destination,'
PRINT 'the color of their suitcase and the dangerous item within the suitcase.'

USE master
GO

CREATE DATABASE PuzzleDatabase
GO

USE PuzzleDatabase
GO

CREATE PROCEDURE PropagateUniqueInformation
AS
BEGIN
   DECLARE @myExecuteAgainFlag BIT

   DECLARE @myDistinctCount INT
   DECLARE @myDistinctValue VARCHAR(10)

   SET @myExecuteAgainFlag = 0

   -- Husbands and Wives

   SELECT @myDistinctCount = COUNT (DISTINCT Wife)
   FROM PuzzleTable
   WHERE Husband = 'Adam'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Wife
      FROM PuzzleTable
      WHERE Husband = 'Adam'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Adam' AND Wife = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Wife)
   FROM PuzzleTable
   WHERE Husband = 'Bill'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Wife
      FROM PuzzleTable
      WHERE Husband = 'Bill'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Bill' AND Wife = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END
 
   SELECT @myDistinctCount = COUNT (DISTINCT Wife)
   FROM PuzzleTable
   WHERE Husband = 'Chad'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Wife
      FROM PuzzleTable
      WHERE Husband = 'Chad'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Chad' AND Wife = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Wife)
   FROM PuzzleTable
   WHERE Husband = 'Dave'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Wife
      FROM PuzzleTable
      WHERE Husband = 'Dave'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Dave' AND Wife = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Wife)
   FROM PuzzleTable
   WHERE Husband = 'Eric'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Wife
      FROM PuzzleTable
      WHERE Husband = 'Eric'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Eric' AND Wife = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   -- Husbands and Destinations

   SELECT @myDistinctCount = COUNT (DISTINCT Destination)
   FROM PuzzleTable
   WHERE Husband = 'Adam'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Destination
      FROM PuzzleTable
      WHERE Husband = 'Adam'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Adam' AND Destination = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Destination)
   FROM PuzzleTable
   WHERE Husband = 'Bill'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Destination
      FROM PuzzleTable
      WHERE Husband = 'Bill'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Bill' AND Destination = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END
 
   SELECT @myDistinctCount = COUNT (DISTINCT Destination)
   FROM PuzzleTable
   WHERE Husband = 'Chad'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Destination
      FROM PuzzleTable
      WHERE Husband = 'Chad'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Chad' AND Destination = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Destination)
   FROM PuzzleTable
   WHERE Husband = 'Dave'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Destination
      FROM PuzzleTable
      WHERE Husband = 'Dave'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Dave' AND Destination = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Destination)
   FROM PuzzleTable
   WHERE Husband = 'Eric'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Destination
      FROM PuzzleTable
      WHERE Husband = 'Eric'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Eric' AND Destination = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   -- Husbands and Colors

   SELECT @myDistinctCount = COUNT (DISTINCT Color)
   FROM PuzzleTable
   WHERE Husband = 'Adam'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Color
      FROM PuzzleTable
      WHERE Husband = 'Adam'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Adam' AND Color = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Color)
   FROM PuzzleTable
   WHERE Husband = 'Bill'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Color
      FROM PuzzleTable
      WHERE Husband = 'Bill'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Bill' AND Color = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END
 
   SELECT @myDistinctCount = COUNT (DISTINCT Color)
   FROM PuzzleTable
   WHERE Husband = 'Chad'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Color
      FROM PuzzleTable
      WHERE Husband = 'Chad'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Chad' AND Color = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Color)
   FROM PuzzleTable
   WHERE Husband = 'Dave'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Color
      FROM PuzzleTable
      WHERE Husband = 'Dave'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Dave' AND Color = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Color)
   FROM PuzzleTable
   WHERE Husband = 'Eric'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Color
      FROM PuzzleTable
      WHERE Husband = 'Eric'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Eric' AND Color = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   -- Husbands and Items

   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Husband = 'Adam'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Husband = 'Adam'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Adam' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Husband = 'Bill'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Husband = 'Bill'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Bill' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END
 
   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Husband = 'Chad'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Husband = 'Chad'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Chad' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Husband = 'Dave'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Husband = 'Dave'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Dave' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Husband = 'Eric'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Husband = 'Eric'
      DELETE FROM PuzzleTable
      WHERE Husband != 'Eric' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   -- Wives and Destinations

   SELECT @myDistinctCount = COUNT (DISTINCT Destination)
   FROM PuzzleTable
   WHERE Wife = 'Annabell'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Destination
      FROM PuzzleTable
      WHERE Wife = 'Annabell'
      DELETE FROM PuzzleTable
      WHERE Wife != 'Annabell' AND Destination = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Destination)
   FROM PuzzleTable
   WHERE Wife = 'Beatrice'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Destination
      FROM PuzzleTable
      WHERE Wife = 'Beatrice'
      DELETE FROM PuzzleTable
      WHERE Wife != 'Beatrice' AND Destination = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END
 
   SELECT @myDistinctCount = COUNT (DISTINCT Destination)
   FROM PuzzleTable
   WHERE Wife = 'Christin'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Destination
      FROM PuzzleTable
      WHERE Wife = 'Christin'
      DELETE FROM PuzzleTable
      WHERE Wife != 'Christin' AND Destination = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Destination)
   FROM PuzzleTable
   WHERE Wife = 'Dorothea'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Destination
      FROM PuzzleTable
      WHERE Wife = 'Dorothea'
      DELETE FROM PuzzleTable
      WHERE Wife != 'Dorothea' AND Destination = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Destination)
   FROM PuzzleTable
   WHERE Wife = 'Elleonor'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Destination
      FROM PuzzleTable
      WHERE Wife = 'Elleonor'
      DELETE FROM PuzzleTable
      WHERE Wife != 'Elleonor' AND Destination = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   -- Wives and Colors

   SELECT @myDistinctCount = COUNT (DISTINCT Color)
   FROM PuzzleTable
   WHERE Wife = 'Annabell'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Color
      FROM PuzzleTable
      WHERE Wife = 'Annabell'
      DELETE FROM PuzzleTable
      WHERE Wife != 'Annabell' AND Color = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Color)
   FROM PuzzleTable
   WHERE Wife = 'Beatrice'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Color
      FROM PuzzleTable
      WHERE Wife = 'Beatrice'
      DELETE FROM PuzzleTable
      WHERE Wife != 'Beatrice' AND Color = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END
 
   SELECT @myDistinctCount = COUNT (DISTINCT Color)
   FROM PuzzleTable
   WHERE Wife = 'Christin'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Color
      FROM PuzzleTable
      WHERE Wife = 'Christin'
      DELETE FROM PuzzleTable
      WHERE Wife != 'Christin' AND Color = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Color)
   FROM PuzzleTable
   WHERE Wife = 'Dorothea'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Color
      FROM PuzzleTable
      WHERE Wife = 'Dorothea'
      DELETE FROM PuzzleTable
      WHERE Wife != 'Dorothea' AND Color = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Color)
   FROM PuzzleTable
   WHERE Wife = 'Elleonor'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Color
      FROM PuzzleTable
      WHERE Wife = 'Elleonor'
      DELETE FROM PuzzleTable
      WHERE Wife != 'Elleonor' AND Color = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   -- Wives and Items

   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Wife = 'Annabell'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Wife = 'Annabell'
      DELETE FROM PuzzleTable
      WHERE Wife != 'Annabell' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Wife = 'Beatrice'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Wife = 'Beatrice'
      DELETE FROM PuzzleTable
      WHERE Wife != 'Beatrice' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END
 
   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Wife = 'Christin'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Wife = 'Christin'
      DELETE FROM PuzzleTable
      WHERE Wife != 'Christin' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Wife = 'Dorothea'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Wife = 'Dorothea'
      DELETE FROM PuzzleTable
      WHERE Wife != 'Dorothea' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Wife = 'Elleonor'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Wife = 'Elleonor'
      DELETE FROM PuzzleTable
      WHERE Wife != 'Elleonor' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   -- Destinations and Colors

   SELECT @myDistinctCount = COUNT (DISTINCT Color)
   FROM PuzzleTable
   WHERE Destination = 'China'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Color
      FROM PuzzleTable
      WHERE Destination = 'China'
      DELETE FROM PuzzleTable
      WHERE Destination != 'China' AND Color = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Color)
   FROM PuzzleTable
   WHERE Destination = 'France'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Color
      FROM PuzzleTable
      WHERE Destination = 'France'
      DELETE FROM PuzzleTable
      WHERE Destination != 'France' AND Color = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END
 
   SELECT @myDistinctCount = COUNT (DISTINCT Color)
   FROM PuzzleTable
   WHERE Destination = 'Greece'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Color
      FROM PuzzleTable
      WHERE Destination = 'Greece'
      DELETE FROM PuzzleTable
      WHERE Destination != 'Greece' AND Color = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Color)
   FROM PuzzleTable
   WHERE Destination = 'Italy'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Color
      FROM PuzzleTable
      WHERE Destination = 'Italy'
      DELETE FROM PuzzleTable
      WHERE Destination != 'Italy' AND Color = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Color)
   FROM PuzzleTable
   WHERE Destination = 'Japan'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Color
      FROM PuzzleTable
      WHERE Destination = 'Japan'
      DELETE FROM PuzzleTable
      WHERE Destination != 'Japan' AND Color = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   -- Destinations and Items

   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Destination = 'China'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Destination = 'China'
      DELETE FROM PuzzleTable
      WHERE Destination != 'China' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Destination = 'France'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Destination = 'France'
      DELETE FROM PuzzleTable
      WHERE Destination != 'France' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END
 
   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Destination = 'Greece'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Destination = 'Greece'
      DELETE FROM PuzzleTable
      WHERE Destination != 'Greece' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Destination = 'Italy'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Destination = 'Italy'
      DELETE FROM PuzzleTable
      WHERE Destination != 'Italy' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Destination = 'Japan'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Destination = 'Japan'
      DELETE FROM PuzzleTable
      WHERE Destination != 'Japan' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   -- Colors and Items

   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Color = 'Blue'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Color = 'Blue'
      DELETE FROM PuzzleTable
      WHERE Color != 'Blue' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Color = 'Green'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Color = 'Green'
      DELETE FROM PuzzleTable
      WHERE Color != 'Green' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END
 
   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Color = 'Red'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Color = 'Red'
      DELETE FROM PuzzleTable
      WHERE Color != 'Red' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Color = 'White'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Color = 'White'
      DELETE FROM PuzzleTable
      WHERE Color != 'White' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   SELECT @myDistinctCount = COUNT (DISTINCT Item)
   FROM PuzzleTable
   WHERE Color = 'Yellow'
   IF @myDistinctCount = 1
   BEGIN
      SELECT @myDistinctValue = Item
      FROM PuzzleTable
      WHERE Color = 'Yellow'
      DELETE FROM PuzzleTable
      WHERE Color != 'Yellow' AND Item = @myDistinctValue
      IF @@rowcount > 0
      BEGIN
         SET @myExecuteAgainFlag = 1
      END
   END

   -- Epilogue

   IF @myExecuteAgainFlag = 0
   BEGIN
      RETURN
   END

   EXEC PropagateUniqueInformation
END
GO

CREATE TABLE PuzzleTable
(
   Husband     VARCHAR(10),
   Wife        VARCHAR(10),
   Destination VARCHAR(10),
   Color       VARCHAR(10),
   Item        VARCHAR(10)
)
GO

CREATE TABLE HusbandTable     (HusbandColumn     VARCHAR(10))
GO
CREATE TABLE WifeTable        (WifeColumn        VARCHAR(10))
GO
CREATE TABLE DestinationTable (DestinationColumn VARCHAR(10))
GO
CREATE TABLE ColorTable       (ColorColumn       VARCHAR(10))
GO
CREATE TABLE ItemTable        (ItemColumn        VARCHAR(10))
GO

PRINT ''
PRINT 'The names of the husbands in alphabetical order are:'
PRINT 'Adam, Bill, Chad, Dave, Eric.'

INSERT INTO HusbandTable (HusbandColumn) VALUES ('Adam')
GO
INSERT INTO HusbandTable (HusbandColumn) VALUES ('Bill')
GO
INSERT INTO HusbandTable (HusbandColumn) VALUES ('Chad')
GO
INSERT INTO HusbandTable (HusbandColumn) VALUES ('Dave')
GO
INSERT INTO HusbandTable (HusbandColumn) VALUES ('Eric')
GO

PRINT ''
PRINT 'The names of the wives in alphabetical order are:'
PRINT 'Annabell, Beatrice, Christin, Dorothea, Elleonor.'

INSERT INTO WifeTable (WifeColumn) VALUES ('Annabell')
GO
INSERT INTO WifeTable (WifeColumn) VALUES ('Beatrice')
GO
INSERT INTO WifeTable (WifeColumn) VALUES ('Christin')
GO
INSERT INTO WifeTable (WifeColumn) VALUES ('Dorothea')
GO
INSERT INTO WifeTable (WifeColumn) VALUES ('Elleonor')
GO

PRINT ''
PRINT 'The destinations in alphabetical order are:'
PRINT 'China, France, Greece, Italy, Japan.'

INSERT INTO DestinationTable (DestinationColumn) VALUES ('China')
GO
INSERT INTO DestinationTable (DestinationColumn) VALUES ('France')
GO
INSERT INTO DestinationTable (DestinationColumn) VALUES ('Greece')
GO
INSERT INTO DestinationTable (DestinationColumn) VALUES ('Italy')
GO
INSERT INTO DestinationTable (DestinationColumn) VALUES ('Japan')
GO

PRINT ''
PRINT 'The colors of the suitcases in alphabetical order are:'
PRINT 'Blue, Green, Red, White, Yellow.'

INSERT INTO ColorTable (ColorColumn) VALUES ('Blue')
GO
INSERT INTO ColorTable (ColorColumn) VALUES ('Green')
GO
INSERT INTO ColorTable (ColorColumn) VALUES ('Red')
GO
INSERT INTO ColorTable (ColorColumn) VALUES ('White')
GO
INSERT INTO ColorTable (ColorColumn) VALUES ('Yellow')
GO

PRINT ''
PRINT 'The dangerous items in alphabetical order are:'
PRINT 'Cutter, Hammer, Knife, Pistol, Wrench.'

INSERT INTO ItemTable (ItemColumn) VALUES ('Cutter')
GO
INSERT INTO ItemTable (ItemColumn) VALUES ('Hammer')
GO
INSERT INTO ItemTable (ItemColumn) VALUES ('Knife')
GO
INSERT INTO ItemTable (ItemColumn) VALUES ('Pistol')
GO
INSERT INTO ItemTable (ItemColumn) VALUES ('Wrench')
GO

PRINT ''
PRINT 'The following step is the most important one.'
PRINT 'We calculate all posibilities (i.e. the Cartesian product).'
PRINT '(5 husbands) x (5 wives) x (5 destinations) x (5 suitcase colors) x (5 dangerours items) ='
PRINT '= 5^5 possibilities = 3125 possibilities = 3125 rows.'
PRINT 'The SELECT statement does this calculation automatically for us,'
PRINT 'if we do not specify a WHERE clause.'

INSERT INTO PuzzleTable (Husband, Wife, Destination, Color, Item)
SELECT HusbandColumn, WifeColumn, DestinationColumn, ColorColumn, ItemColumn
FROM HusbandTable, WifeTable, DestinationTable, ColorTable, ItemTable
GO

PRINT ''
PRINT 'By monitoring the row count, we will be able to see'
PRINT 'how each restriction diminishes the number of rows/possibilities.'
PRINT 'When all of the restrictions have been acknowledged,'
PRINT 'only 5 rows should remain on the table.'
PRINT 'These 5 rows should correspond to the solution.'

SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '01. The couple that headed to Italy had a hammer in their suitcase.'

DELETE FROM PuzzleTable
WHERE Destination = 'Italy' AND Item != 'Hammer'
GO
DELETE FROM PuzzleTable
WHERE Destination != 'Italy' AND Item = 'Hammer'
GO
EXEC PropagateUniqueInformation
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '02. Elleonor and her husband were going to Japan.'

DELETE FROM PuzzleTable
WHERE Wife = 'Elleonor' AND Destination != 'Japan'
GO
DELETE FROM PuzzleTable
WHERE Wife != 'Elleonor' AND Destination = 'Japan'
GO
EXEC PropagateUniqueInformation
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '03. There was a pistol in the white suitcase.'

DELETE FROM PuzzleTable
WHERE Color = 'White' AND Item != 'Pistol'
GO
DELETE FROM PuzzleTable
WHERE Color != 'White' AND Item = 'Pistol'
GO
EXEC PropagateUniqueInformation
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '04. Eric and Beatrice are married to each other.'

DELETE FROM PuzzleTable
WHERE Husband = 'Eric' AND Wife != 'Beatrice'
GO
DELETE FROM PuzzleTable
WHERE Husband != 'Eric' AND Wife = 'Beatrice'
GO
EXEC PropagateUniqueInformation
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '05. Adam and his wife carried a green suitcase.'

DELETE FROM PuzzleTable
WHERE Husband = 'Adam' AND Color != 'Green'
GO
DELETE FROM PuzzleTable
WHERE Husband != 'Adam' AND Color = 'Green'
GO
EXEC PropagateUniqueInformation
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '06. Bill and his wife had a wrench in their suitcase.'

DELETE FROM PuzzleTable
WHERE Husband = 'Bill' AND Item != 'Wrench'
GO
DELETE FROM PuzzleTable
WHERE Husband != 'Bill' AND Item = 'Wrench'
GO
EXEC PropagateUniqueInformation
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '07. The couple that was going to Greece had a green suitcase.'

DELETE FROM PuzzleTable
WHERE Destination = 'Greece' AND Color != 'Green'
GO
DELETE FROM PuzzleTable
WHERE Destination != 'Greece' AND Color = 'Green'
GO
EXEC PropagateUniqueInformation
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '08. Annabell and her husband were heading to China.'

DELETE FROM PuzzleTable
WHERE Wife = 'Annabell' AND Destination != 'China'
GO
DELETE FROM PuzzleTable
WHERE Wife != 'Annabell' AND Destination = 'China'
GO
EXEC PropagateUniqueInformation
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '09. The red suitcase contained a wrench.'

DELETE FROM PuzzleTable
WHERE Color = 'Red' AND Item != 'Wrench'
GO
DELETE FROM PuzzleTable
WHERE Color != 'Red' AND Item = 'Wrench'
GO
EXEC PropagateUniqueInformation
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '10. Chad and Christin are married.'

DELETE FROM PuzzleTable
WHERE Husband = 'Chad' AND Wife != 'Christin'  
GO
DELETE FROM PuzzleTable
WHERE Husband != 'Chad' AND Wife = 'Christin'
GO
EXEC PropagateUniqueInformation
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '11. Beatrice and her husband were carrying a knife in their suitcase.'

DELETE FROM PuzzleTable
WHERE Wife = 'Beatrice' AND Item != 'Knife'
GO
DELETE FROM PuzzleTable
WHERE Wife != 'Beatrice' AND Item = 'Knife'
GO
EXEC PropagateUniqueInformation
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '12. Chad and his wife carried a yellow suitcase.'

DELETE FROM PuzzleTable
WHERE Husband = 'Chad' and Color != 'Yellow'
GO
DELETE FROM PuzzleTable
WHERE Husband != 'Chad' and Color = 'Yellow'
GO
EXEC PropagateUniqueInformation
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '13. Dave and Annabell are married.'

DELETE FROM PuzzleTable
WHERE Husband = 'Dave' and Wife != 'Annabell'
GO
DELETE FROM PuzzleTable
WHERE Husband != 'Dave' and Wife = 'Annabell'
GO
EXEC PropagateUniqueInformation
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '14. The cutter was in the green suitcase.'

DELETE FROM PuzzleTable
WHERE Color = 'Green' and Item != 'Cutter'
GO
DELETE FROM PuzzleTable
WHERE Color != 'Green' and Item = 'Cutter'
GO
EXEC PropagateUniqueInformation
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT '15. Dorothea and her husband were not going to France.'

DELETE FROM PuzzleTable
WHERE Wife = 'Dorothea' and Destination = 'France'
GO
EXEC PropagateUniqueInformation
GO
SELECT COUNT(*) FROM PuzzleTable
GO

PRINT ''
PRINT 'The 5 rows that should remain on the table,'
PRINT 'i.e. the solution, should be:'
PRINT '----------------------------------'
PRINT 'Adam Dorothea Greece Green  Cutter'
PRINT 'Bill Elleonor Japan  Red    Wrench'  
PRINT 'Chad Christin Italy  Yellow Hammer'
PRINT 'Dave Annabell China  White  Pistol'
PRINT 'Eric Beatrice France Blue   Knife'
PRINT '----------------------------------'

SELECT * FROM PuzzleTable
GO

USE master
GO

DROP DATABASE PuzzleDatabase
GO

Here is the results tab after running the previous script:

SQL2

Posted in SQL Server, Uncategorized

How jectivity corresponds to morphisms

“Jectivity” may or may not be a real word in the dictionary and my command of the English language is not adequate for me to make such a discussion.

But “jectivity” is indeed a valid mathematical word and it concerns the classification of functions into injective, surjective, and bijective ones.

But before we discuss jectivity, let us discuss functions. What is a function and what is not a function?

A function maps all elements from its domain to its codomain. Any element from the domain is mapped to only one element from the codomain.

This is a function:

Slide1

This is not a function, because an element from the domain is not mapped:

Slide2

This is not a function, because an element from the domain is mapped to more than one element in the codomain:

Slide3

Now let us classify functions into injective, surjective, and bijective ones.

Please note that the following analysis is based on numerous Wikipedia articles on functions and morphisms.

An injective function (or injection) maps any element of the domain to a different element in the codomain.

A surjective function (or surjection) maps to all elements of the codomain.

A bijective function (or bijection) is both injective and surjective.

Example:

Slide4

A function f: A -> B is injective if and only if f is left-invertible; that is, there is a function g: f(A) -> A such that g o f = identity function on A.
A function f: X -> Y is injective if and only if it is left-cancellative; that is, given any functions g1 ,g2 : Y -> Z, f o g1 = f o g2 => g1 = g2.

A function f: A -> B is surjective if and only if it is right-invertible; that is, there is a function g: B -> A such that f o g = identity function on B.
A function f: X -> Y is surjective if and only if it is right-cancellative; that is, given any functions g1, g2 : Y -> Z, g1 o f = g2 o f => g1 = g2.

A function f: A -> B is bijective if and only if it is invertible; that is, there is a function g: B -> A such that g o f = identity function on A and f o g = identity function on B.

The composition of two bijections is again a bijection, but if g o f is a bijection, then it can only be concluded that f is injective and g is surjective.

Injections, surjections, and bijections loosely correspond to Category Theory’s monomorphisms, epimorphisms, and isomorphisms, respectively.

A monomorphism (also called a monic morphism or a mono) is a morphism f: X -> Y that is left-cancellative in the sense that, for all morphisms g1, g2 : Z -> X, f o g1 = f o g2 => g1 = g2.

An epimorphism (also called an epic morphism or an epi) is a morphism f: X -> Y that is right-cancellative in the sense that, for all morphisms g1, g2 : Y -> Z, g1 o f = g2 o f => g1 = g2.

An isomorphism is both a monomorphism and an epimorphism.

A morphism f : X -> Y in a category is an isomorphism if it has a two-sided inverse; that is, there is another morphism g : Y -> X in that category such that g o f = 1X and f o g = 1Y, where 1X and 1Y are the identity morphisms of X and Y, respectively.

I think that this analysis could be used as the introduction to a primer in Category Theory.

Posted in Science

Absolute URLs vs. relative URLs vs. protocol relative URLs

Examples

Absolute URL:
http://yoursite.com/folder/subfolder/file.html
Relative URL:
/folder/subfolder/file.html
Protocol relative URL:
//anothersite.com/anotherfolder/anothersubfolder/anotherfile.html

Tips

  • Try to avoid absolute URLs.
  • Try to use relative URLs for links inside your site.
  • Try to use protocol relative URLs for links outside your site.
Posted in Web design

Venn diagrams vs. Euler diagrams

In Venn diagrams, all areas (subsets) are shown. Areas that contain no elements (empty subsets) are filled with black color.

In Euler diagrams, only areas that contain elements (non-empty subsets) are shown.

If we want to depict all areas, irrespectively of whether they contain elements or not, We should choose to make a Venn diagram.

If we want to avoid depicting areas that contain no elements, and instead focus only on the areas that are non-empty, we should choose to make an Euler diagram.

Venn diagrams vs. Euler diagrams

Posted in Science

Arrow talk

On the Stack Overflow site, I found a great question titled Monads vs. Arrows. Essentially the OP (original poster) asks: “… When should I use monads and when should I use arrows?”.

I answered the question and since I believe that I raise some important points in my answer, I decided to duplicate my answer here as well. My answer follows:

The short answer is that Arrows are more general than Monads and are also more cumbersome to use. Thus you should use Monads whenever you can, leaving the use of Arrows for the cases where Monads are not applicable.

The “scenic route” answer follows.

John Hughes, the person who introduced Arrows, has published two great papers that I recommend: “Generalising monads to arrows” and “Programming with Arrows”. These two articles are easy to read and provide the answer to your question. Even if some people do not understand all the details or the code in these two articles, they will certainly find lots of information and very helpful explanations about Monads and Arrows.

I will now highlight the main points from these articles that pertain to your question.

When Monads were introduced, people thought that they were all-powerful. Indeed, Monads pack a lot of power. But at some point, it was found that there are cases where Monads cannot be applied. These cases have to do with multiple inputs, especially when some of the inputs are static and some of the inputs are dynamic. So, John Hughes stepped up and introduced Arrows.

Arrows are more general than Monads. Arrows are a superset of Monads. They can do all that Monads do and more. But they are also more difficult to use. John Hughes recommends that you should use Monads whenever you can and that you should use Arrows when you cannot use Monads.

I agree with John Hughes. I am also reminded of Einstein’s quote “Everything should be made as simple as possible, but not simpler”.

Of course, it all depends on the particular situation at hand. Let me explain. Let us suppose that you are learning Haskell. Then it would be a great task to do each program using a monadic approach and redo it using an arrow-based approach. When you learn, you should strive to explore all possibilities and implement all kinds of approaches. This way, you obtain great insight and you are able to compare different solutions first-hand.

Now let us suppose that you want to provide a library to the community. Well, you owe it to the people that will read your code that you should use the approach that is easiest to understand and still gets the job done. You also owe it to the people that will use your code that your solution lacks unnecessary complexity. This way, your solution is more easily maintainable and less prone to errors and bugs.

But what if you are in a borderline case? Let us suppose that you are not sure whether or not you will need the extra power of Arrows. Then what should you do? Should you start with a monadic approach and later switch to an arrow-based one if the need arises? Or should you start with Arrows from the get-go, avoiding a costly switch halfway through the project?

Again, my answer is to try the first approach: try to use Monads if you can. If you later find out that you cannot use Monads, you will have to endure a costly switch, where you will have to restart and redo the project in order to use Arrows. This approach will certainly require more time and other resources from your part. But you will know that you did the correct thing, which was to try to provide the simplest, clearest, less complex solution possible.

Avoiding unnecessary complexity is the most important thing. Believe it or not, this is the reason concepts (such as function composition, Monads and Arrows) from Category Theory were introduced to Computer Science. Ironic?

Posted in Development

Cheat sheet for Monads in Haskell

Let M be a Type Constructor, Functor, and Monad.

As a Type Constructor, M can map a type a to the type M a.

As a Functor, M can also map a function f to the function M f, using M’s fmap function that we must provide.

As a Monad, M has a Natural Transformation μ :: M2 -> M, where M2 = M o M. We will see how this makes possible the composition of a function a – > M b and a function b -> M c.

If we have a function g :: a -> b and a function f :: b -> c, then we can compose these two functions. Their composition is the function f o g :: a -> c.

f o g is calculated as follows: a -> b -> c. In other words, the input of function g is the input of f o g, the output of function g is used as input to the function f, and the output of function f is the output of f o g.

But we cannot use “normal” composition when the functions g and f are of the following form:

g :: a -> M b
f :: b -> M c

In this case, to “compose” these two functions we need to define a “special” composition. Let us call this special composition “bind” and let its symbol be >>= so that g >>= f is this special composition. Thus, bind takes the output of function g, passes it function f, and produces as output the output of function f. Thus (>>=) :: M b -> (b -> M c) -> M c. Since b and c are any types, we can use a and b instead of b and c. Thus: ( >>=) :: M a -> (a -> M b) -> M b.

Thus, bind is defined as M a -> (a -> M b) -> M b. Now let us see what bind is equal to. Let:

g :: a -> M b
f :: b -> M c

Thus M f :: M b -> M2 c, where M2 = M o M.

In the previous line, M was used as a Functor. M f is also known as fmap f.

As a Monad, M has a Natural Transformation μ­­a :: M2 a -> M a. Since this holds true for any type, we use c instead of a, thus μ­­­c :: M2 c -> M c. μ is also known as join.

We can now find the result of the special composition between g and f and what bind is equal to.

g >>= f is calculated as follows: a -> M b -> M2 c -> M c.

Thus >>= is equal to μc o (M f) o g.

Thus bind = join o (fmap f) o g.

By using the special composition bind (>>=), we are able to compose two functions that are NOT of types a-> b and b -> c, but are of types a -> M b and b -> M c.

Posted in Development

The most significant FAQs about Haskell

Question: Function application and composition versus bind (>>=)

Answer: For the following discussion, a, b, and c are built in Haskell data types.

We use normal function composition when we compose a function a -> b with a function b -> c. The result is a function with a type signature of a -> c and with an output of type c.

We use bind when we compose a function a -> M b with a function b -> M c. The result is a function a -> M c. M is a Monad and bind is a function that a Monad has to have and that instructs on how such a composition is to be made. Someone has to provide the code for bind. The type signature for bind is M a -> (a -> M b) -> M b. Since a, b, and c are arbitrary types, this can be written equivalently as M b -> (b -> M c) -> M c. Thus we see that bind takes the output of a function a -> M b and a function b -> M c and composes them producing the output M c.

Question: let versus <-

Answer: First of all, let and <- are not interchangeable; they perform differently.

The <- statement has to have a Monad on its right side and it will extract the value from that Monad.

The let statement is just assignment. It does not extract anything from its right side and its right side can have any type (even a Monad).

Here is a program that demonstrates the use of the <- operator:

module Main where

import Data.Typeable

myFunction   :: String -> IO Int
myFunction xs =
   do
     putStrLn "Inside the function that returns the length of a string plus 10."
     return ((length xs) + 10) 

main :: IO ()
main  =
   do
     putStrLn "Program begins."

     a <- myFunction "Dimitrios Kalemis"
     print a
     print (typeOf a)
     print (typeOf myFunction)

     putStrLn "Program ends."

The <- statement is syntactic sugar used in the do notation. The following two programs are equivalent:

First program:

module Main where 

main :: IO ()
main  =
   do
     nameVariable <- getLine
     putStrLn ("You typed: " ++ nameVariable)

Second program:

module Main where 

main :: IO ()
main  = getLine >>= \nameVariable -> putStrLn ("You typed: " ++ nameVariable)

The StackOverflow entry “<-” bindings in do notation has excellent answers concerning this matter.

Question: data versus type versus newtype

Answer: The data declaration is used for the creation of new types.

The type declaration is used for the creation of type synonyms for existing types.

The newtype declaration is almost like the data declaration. The newtype declaration and the data declaration have some differences.

The underlying reason for these differences is that types declared with the data keyword are lifted – that is, they contain their own bottom (⊥) value that is distinct from all the others. (The term bottom refers to a computation which never completes successfully.) Thus, Haskell provides the newtype keyword, for the construction of unlifted types.

This fact leads to the following two differences:

  • Although you can replace the newtype keyword with the data keyword, the converse is not true: the data keyword can only be replaced with newtype if the type has exactly one value constructor with exactly one field inside it.
  • The value constructor introduced by data is lazy (thus carries more overhead) than the value constructor introduced by newtype which is strict (thus faster).

For more information I recommend the following two sources:

More insight on this issue can be found in John Hughes’ excellent paper “Generalising monads to arrows”. In paragraph 2.2, John Hughes describes the State Monad. He writes:

In this case we represent a computation with result type a and a state of type s by a value of the type
newtype StateMonad s a = SM (s -> (a,s))

For the newtype declaration, John Hughes provides following footnote:

The Haskell newtype declaration introduces a new type isomorphic to an existing one, where the constructor names the isomorphism. Its purpose is to enable us to define overloaded operations which behave differently on the new type and the old. In this case, we will define the monad operations for StateMonad quite independently of any definition that may be given for functions. The difference between a newtype and data declaration is subtle, but quite important for efficiency: at run-time, a value of a type defined by newtype is represented in exactly the same way as the type it is isomorphic to – the constructor is not represented at all – whereas the constructors of a data type are always represented explicitly.

Posted in Development