Solving Sudoku in One SQL Query – Part 2 – Creating the Framework

In this post, I’ll be diving deep into the code that was presented in this post.

Recursive CTEs

My solution utilizes a lot of recursive common table expressions (CTEs). CTEs are a simple way of defining a temporary projection in T-SQL that can be referenced multiple times later on in a query. Their real power, however, lies in their ability to be self-referencing and thus recursive. In a recursive CTE, we define an initial projection and UNION ALL that with a projection that references the table currently being defined.

Since this puzzle is all about digits 1 through 9, I need to make something that will get me those values to work with.

This is an easy way to get the digits we need without having to list them all out. The first statement in the expression gives the basis of the recursion (1), then we UNION ALL to the Cnt table, selecting the value in the table + 1. Initially Cnt has a single record with [val] = 1. Then we union that with a record that is [val] + 1 = 2. This continues until the constraint on the second selection is no longer true. Once [val] = 9, we cannot union it again and we end up with a table of values 1 through 9.

Assigning Each Cell

Next, I want to get a set of all the possible locations in the grid with values ranging from 1 to 81. I could do another CTE like the one I just did, but I already have values 1 to 9, I can utilize my Cnt table to create my location table.

Assigning Cells to Groups

In the game of Sudoku, each cell contains a digit that is unique within the row, column, and square that the cell is a member of. In order to facilitate checking that the value is unique, we will create a table that defines all the groups that each cell is a member of. The row and column groups are fairly easy to define, but the nine 3×3 boxes are a bit more difficult. In order to better set these groupings apart, I prefix the row groupings with a 10, the column groupings with a 20 and the box groupings with a 30.

This will allow us to cross-reference any locations to see if a particular value already exists. For instance, if I’m looking at the value in location 19, I’ll need to look at all the locations that are part of the groupings 103, 201, and 301 to see if the value I want to put in that location is already in any of the other locations in those groups.

The first two select clauses are retrieving the row and column groupings respectively, then the third grouping is creating groups for the nine 3×3 boxes in the grid. With these available to us, the job of building up a valid solution will be much easier.

Now I have all the framework I need to begin solving the sudoku puzzle. I have each of the 9 digits that I need; I have have given each cell in the grid a unique value; and I have made a listing of the groupings of cells that need to contain each of the 9 digits. In the next post I will walk through the code that takes the given values and builds out the correct solution.


Leave a Reply

Your email address will not be published.

Please type the characters of this captcha image in the input box

Please type the characters of this captcha image in the input box