Most of the fn_sudoku function's logic is introduced in the loop at callout C in Listing 4. You basically write two types of rules. First, you write rules that delete from @SudokuNon-Unique those values that can't be correct. Then, you write rules that insert the final correct values into @SudokuUnique. (I give examples of delete and insert rules in the next section.)
At the beginning of the loop, the @rc variable is initialized with zero. Then, each delete and insert rule increments the @rc variable with the number of rows affected by the rule. The loop continues as long as rules affect rows in the previous round. Finally, the fn_sudoku function loads into the @Sudoku table variable (which is the function's output parameter) all final values from @SudokuUnique and nonfinal lists from @SudokuNonUnique.
To test the function after adding each rule, it's convenient to examine the output in a pivoted form (one row for each Sudoku row), where each cell contains a concatenated list of the remaining values. The code in Listing 5 pivots and concatenates the output from the fn_sudoku function.
In Listing 5, the SudokuStrings CTE converts the val column values returned from the function into character strings because you need to concatenate multiple values. The SudokuPivotVals CTE pivots multiple values of the same cell (row/col) and concatenates them into a comma-separated list of values. The SudokuPivotVals2 CTE removes the trailing comma. The SudokuPivotCols CTE pivots columns of the same row, so that you get nine different columns in the same result row.
To test the code, you can run it using the function's implementation, which doesn't apply any rules yet. Table 1 shows the abbreviated output. All occupied cells from SudokuInput show up as scalar values. Unoccupied cells from SudokuInput currently show up as lists—that is, 1,2,3,4,5,6,7,8,9. However, for brevity, I replaced the string 1,2,3,4,5, 6,7,8,9 with the string 1-9 in Table 1.
Adding Rules
Now it's time to implement the brains of the fn_sudoku function by identifying and writing its delete and insert rules. I'll give a few sample rules, then leave it up to you to add others.
Listing 6 shows sample delete rules that remove values from @SudokuNonUnique. If a cell is occupied in @SudokuUnique, its value is final. So, the first rule removes all potential values from the corresponding cell in @SudokuNonUnique. The second rule removes values that appear in the same row, column, or box in @SudokuUnique.
To test these delete rules, you can add the code in Listing 6 to the function's loop body at callout C in Listing 4, then run the formatting code in Listing 5. Table 2 shows the results. As you can see, the lists got smaller.
Listing 7 shows sample insert rules that load final values into @SudokuUnique. This code works by isolating values in @SudokuNonUnique from cells that aren't populated yet in @SudokuUnique (same row and col; doesn't exist in @SudokuUnique). The first rule isolates values from @SudokuNonUnique that became unique in their cell after applying the delete rules. A value is unique in its cell if there's no other value in the same cell (same row and col; different value). The second rule isolates values that can't appear in another cell in the same row. The logic of this rule is a bit tricky, but if you've practiced relational division logic, this logic should be familiar to you. The T-SQL expression that applies the second rule basically translates to the following pseudocode:
Isolate the value if you can't find
(the same value in another
unoccupied cell in the same row
for which you can't find
(a final occupied cell with
the same value and
(the same row, column, or
cube)))
The third rule isolates values that can't appear in another cell in the same column. The fourth rule isolates values that can't appear in another cell in the same box.
To test these insert rules, you can add the code in Listing 7 to the function's loop at callout C in Listing 4, then run the code in Listing 5 to generate formatted output. As Figure 2 shows, the delete and insert rules that I provided are sufficient to solve this Sudoku puzzle as well as solve other Sudoku puzzles.
Putting It All Together
The solution that I've provided contains the framework for solving Sudoku puzzles and some sample fundamental rules. You can continue improving the solution by identifying and implementing more rules. In this article's 47752.zip file, which you can download at InstantDoc ID 47752, you'll find sudoku.sql, which contains the code in the seven listings.
Sudoku.sql also contains the input for another Sudoku puzzle in case you want to try to solve one on your own. The sample rules in Sudoku.sql don't solve this puzzle completely, so you need to do some logical thinking to come up with the solution. In the 47752.zip file, you'll find the input for this puzzle (Figure A) as well as the solved puzzle (Figure B).
Keep On Thinking
Handling Sudoku puzzles with T-SQL is a great way to practice logic and logic programming at the same time. I also recommend that you try to solve Sudoku puzzles manually. Not only will you hone your logic skills, but you'll probably also have some fun in the process.
End of Article
Prev. page
1
[2]
next page -->
