One is a brute-force approach in which you try different permutations and check for validity or invalidity. There are two main approaches that you can take in programming a solution to Sudoku puzzles. In my code, I like to use the normalized form because I find it much more convenient for set manipulation. The code at callout B shows how to generate a normalized form of the input from the denormalized SudokuInputD table. The code at callout A in Listing 3 shows how to generate a denormalized form of the input from the normalized SudokuInput table. Note that with the new PIVOT and UNPIVOT operators, you can easily generate one form from the other. The code in Listing 2 creates a denormalized table named SudokuInputD and populates it with the sample data in Figure 1. Some programmers prefer to store the input in a denormalized form, where each row in the table represents a row in the input puzzle. This code loads the table with only those rows that represent populated cells. The code in Listing 1 creates a normalized table named SudokuInput and populates it with the sample data in Figure 1. I like to use a normalized table to store input for a Sudoku puzzle. You can learn about CTEs in the T-SQL Black Belt articles "Cycling with CTEs (June 2004, InstantDoc ID 42452) and "Get in the Loop with CTEs" (May 2004, InstantDoc ID 42072). You can find details about the PIVOT and UNPIVOT operators in the Web-exclusive T-SQL 2005 articles "UNPIVOT" (InstantDoc ID 43589), "Dynamic Pivoting" (InstantDoc ID 43140), and "Pivot (or Unpivot) Your Data" (InstantDoc ID 42901). The main T-SQL enhancements that I'll use are the PIVOT and UNPIVOT operators, and Common Table Expressions (CTEs). That way, you'll have a chance to practice both your logic skills and learn how to use the T-SQL enhancements. I thought that it would be interesting to handle Sudoku puzzles with T-SQL, using some of the new features in SQL Server 2005. The variations in complexity have to do with varying levels of logical rules and deductions that you need to apply to solve the puzzle. Sudoku puzzles have varying levels of difficulty, but all require you to apply logical deduction to solve them. Figure 2 shows the solution to the puzzle in Figure 1. Note that in a correctly formed Sudoku puzzle, there can be only one correct solution. The goal is to populate all cells with numbers in the range 1 through 9 so that no number will repeat in the same row, column, or 3×3 box. Some of the cells are already populated with numbers that range from 1 through 9. As Figure 1 shows, in a classic Sudoku puzzle, you get a 9×9 squared grid that's subdivided into 3×3 squared boxes. The Sudoku puzzle has more restrictions than Latin squares. In the late 1980s, the Sudoku puzzle surfaced in Japan. In the 1970s, a form of the puzzle called number place surfaced in America. In Latin squares, you populate a square grid with numbers or symbols that can't repeat in the same row or column. In 1783, Swiss mathematician Leonhard Euler invented Latin squares as a variation of magic squares. However, the concept behind Sudoku puzzles is by no means unique. Sudoku is a Japanese term that refers to a number that's singular or unique. You've probably already heard of the logic puzzle called Sudoku, which is popular these days. In many of my articles, I mention that SQL involves a lot of logic and that you can improve your SQL querying capabilities by solving pure logic puzzles.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |