| Downloads |
|---|
| 98775.zip |
| Executive Summary: The eight queens puzzle is a classic puzzle that challenges you to arrange eight queens on an 8 × 8 chessboard such that no two queens can attack each other based on regular chess rules—that is, that no two queens are in the same row, column, or diagonal. You can use T-SQL to write a statement that returns all possible solutions to this puzzle. |
I recently received an interesting puzzle from Roy Harvey, a friend and fellow SQL Server MVP, that I found to be a good exercise in both logic and T-SQL. After I present the problem, I’ll provide the model that Roy used to solve the puzzle with a computer program. Then, I’ll give you both Roy’s and my T-SQL implementations of the solution. As always, I suggest that you not look at the solution before you try to solve the problem on your own.
The Eight Queens Puzzle
The puzzle is called the eight queens puzzle, and it was first suggested by the chess player Max Bezzel more than 150 years ago. The challenge is to arrange eight queens on an 8 × 8 chessboard such that no two queens can attack each other based on regular chess rules—that is, that no two queens are in the same row, column, or diagonal. Figure 1 shows one possible solution. Your challenge is not to find one possible arrangement, but rather to write a T-SQL solution that returns all possible arrangements.
The Logical Solution
You can use various known algorithms to solve the problem. For details about these solutions, go to en.wikipedia.org/wiki/eight_queens.
One of the most inefficient methods you can use is based on a naive brute force search algorithm in which all possible placements of queens are considered. With 64 cells and 8 queens, this method involves 64^8 (281,474,976,710,656) permutations—including cases in which a cell contains more than one queen. A filtering process eliminates the placements with more than one queen appearing in the same cell, as well as those in which two queens are attacking each other.
Even when using a brute-force algorithm, you can model the problem to reduce the initial number of placements taken into consideration from 64^8 to a substantially smaller number. Then, you just add the remaining filtering logic on top to isolate only qualifying placements.
For example, the model that Roy used in his solution is to represent each placement of eight queens as a string of eight distinct digits. Each digit has one of the values in the range 1 through 8 representing the row in the chessboard, whereas the digit’s position in the string (from left to right) represents the column in the chessboard. So, for example, the solution shown in Figure 1 would be expressed with this model as 17468253—meaning that the placement of the eight queens are: row 1, column 1 (1a); row 7, column 2 (7b); row 4, column 3 (4c); row 6, column 4 (6d); row 8, column 5 (8e); row 2, column 6 (2f); row 5, column 7 (5g); row 3, column 8 (3h).
The simplest solution based on this model is to initially produce all possible strings made of the 8 distinct digits. Surprisingly, this isn’t a large number of permutations—8! = 40,320—especially in database terms. The fact that each string contains 8 distinct digits, where the digit represents a row and a digit position represents a column, already restricts the representation to only one queen per row and one per column. That’s why the initial number of permutations is so small.
What’s left is to filter only the permutations in which no two queens are placed in the same diagonal. This is achieved by ensuring that no two digits in the strings satisfy the following predicate: The absolute difference between the digits is equal to the difference between their positions. For example, in the string 12473685, the representation is such that no two queens are in the same row or column. But the absolute difference between the second and first digits is 1, and the difference between the positions of the digits is 1 as well, meaning that the two queens that those digits represent are placed on the same diagonal. Now that I’ve covered the solution’s logic, I’ll present a couple of T-SQL implementations of the solution.
The T-SQL Implementation
Web Listing 1 shows the T-SQL solution that was written by Roy. The solution first defines a common table expression (CTE) called Eight with a row for each of the eight digits in the range 1 through 8. The column in the CTE that holds the digit is called i. The outer query joins eight instances of the CTE, each of which represents a different column in the chessboard. The names of the instances that are being joined are A through F. For each column that is processed (i.e., each table in the join), a match is produced for each digit (row) in the new column that didn’t appear so far in previous columns. The join condition also filters only cases in which the queen represented by the new digit isn’t placed in the same diagonal with any other queen that appears in previous columns. This is achieved as I explained earlier by checking that no cases exist in which the absolute difference between the digit values is the same as the difference between the digits positions.
For example, the join predicate between the instances A and B is
Eight as A
JOIN Eight as B
ON B.i <> A.i
and (B.i - A.i) NOT IN (-1, +1)
The predicate used to match the result with C is
JOIN Eight as C
ON C.i NOT IN (A.i, B.i)
AND (C.i - A.i) NOT IN (-2, +2)
AND (C.i - B.i) NOT IN (-1, +1)
and so on.
Web Listing 2 shows the T-SQL solution that I wrote. My solution’s logic is very similar to Roy’s, except that instead of explicitly joining eight instances of the numbers table, it uses a recursive CTE, and instead of producing eight different columns, it concatenates a character for each digit in a single string.
There are three predicates in the join performed by the recursive member of the CTE. The first simply ensures that the recursive query will run as long as the string has fewer than 8 digits:
ON PRV.strlen < 8
The second predicate uses pattern matching to ensure that the new digit doesn’t already appear in the string:
AND PRV.string NOT LIKE ‘%’ + CAST(NXT.N AS VARCHAR(1)) + ‘%’
The last predicate ensures that the new queen isn’t placed on the same diagonal as any other queen that is already represented in the string (absolute difference between digit values equal to difference between digit positions):
AND NOT EXISTS
(SELECT *
FROM Nums AS D
WHERE D.n <= PRV.strlen
AND PRV.strlen + 1 - D.n =
ABS(NXT.n - CAST(SUBSTRING(PRV.string, D.n, 1) AS INT)))
For fun, I created the code in Web Listing 3 to randomly choose one of the 92 possible solutions. The code also adds unpivoting and pivoting logic to produce a graphical depiction of the solution, as Web Table 1 shows.
A Useful Exercise
Although the solutions I present to the eight queens puzzle aren’t the most efficient possible solutions, they’re pretty fast—both running in well under a second. This puzzle is very suitable for set-based processing with SQL, especially with brute-force methods in which you need to create permutations. I hope you enjoyed this interesting exercise in T-SQL as much as I did. Many thanks to Roy Harvey for sending me the puzzle.
