Easy - 1 level -36 hint

• 9 X 9 sudoku
  Easy
  1level - 36hint
  2level - 35hint
  3level - 34hint
  4level - 33hint
  5level - 32hint
  6level - 31hint
  Medium
  7level - 30hint
  8level - 29hint
  Hard
  9level - 28hint
  10level - 27hint
  Expert
  11level - 26hint
  12level - 25hint
  Expert - Silver
  13level - 24hint
  14level - 23hint
  15level - 22hint
  16level - 21hint
  17level - 20hint
  Expert - Gold
  18level - 19hint
  19level - 18hint
  20level - 17hint
  

Microsoft Visual Studio Code. Visual Studio Code is a free source code editor for Windows. It comes with built-in support for JavaScript, TypeScript and Node.js and has a rich ecosystem of extensions for other languages (such as C, C#, Python, PHP, Go) and runtimes (such as.NET and Unity).

9 X 9 sudoku

Each game has one correct answer and there are a total of 20 levels of games.

• It turns out that this counterpart ('1') is the same as the cell we originally swapped. This is the termination criterion, as the current state is a valid Sudoku puzzle. Classic VB (vb6) code The code is written in classic vb (vb6).
• Building Sudoku using Windows Presentation Foundation and XAML, Microsoft's new declarative programming language. This is the 1st article from a series of 5 articles and focusses on introducing.

9 squares x 9 squares A total of 81 squares (9x9 = 81) fill in the blanks with numbers from 1 to 9 according to the rules.
We offer games in levels 1-20.

One thing you are almost guaranteed to see on trains these days is at least one person (quite often more) with pencil poised, glassy-eyed, intensely focused on a Sudoku puzzle. These fascinating numbers puzzles have become exceedingly popular in the UK (and goodness knows where else).

I have never been a keen puzzles enthusiast, so I was initially reluctant to check out this new craze. But seeing how people seemed to be enjoying it I finally gave it a go. I found that it was quite easy to understand the rules, get started, and get stuck in! And soon, before I knew what hit me, I was hooked.

You can think of a Sudoku as a square divided into 9 equal squares (blocks) and the 9 squares each further divided into 9 much smaller squares (cells). That makes 9 blocks and 81 cells (see Figure 1).

Figure 1: An example of a Sudoku puzzle

The blocks make a 3 x 3 grid (i.e. 3 rows and 3 columns). The cells make a 9 x 9 grid (i.e. 9 rows and 9 columns).

A Sudoku puzzle comes with numbers already present in some of the cells. The objective of the puzzle is to fill in the remaining cells with the right numbers. The cells must be filled according to the following simple rules:

1. All the 9 cells in each row must have the numbers 1 to 9 with no repetition.
2. All the 9 cells in each column must have the numbers 1 to 9 with no repetition.
3. All the 9 cells within each block must have the numbers 1 to 9 with no repetition.

(‘No repetition’ is purely for emphasis, because if you use all of 1 to 9, and you have only 9 places to fill, there can be no repetition anyway.)

Sudoku comes in varying levels of difficulty and degrees of challenge, depending on which, and how many, cells have been filled in already. Whatever the case, you do not need any kind of serious mathematics or clever mental gymnastics; all you need is your own personal logical reasoning and a determination not to be beaten. That is why they can be so much fun.

To make it even more fun for myself, I embarked on an exercise to write a program that solves Sudoku puzzles. And to make it even more challenging I decided not to write the program in the popular object-oriented fashion (Java, C++, C#, etc.) or in any of the old-fashioned procedural programming languages (Pascal, C, Basic etc); but in Transact SQL, within SQL Server 2000. Basically, I wanted to see how the features of T-SQL can be used to develop something like a Sudoku puzzle solution. I have learnt some useful things from the exercise, which I’m eager to pass on to my fellow programmers.

T-SQL is rich in in-built programming functions and features. Far from being just for holding and manipulating data, T-SQL is a programming language in its own right. Many algorithm-based problems that used to be solved with mainstream procedural or object-oriented languages can now be dealt with completely within SQL Server using T-SQL, because not only does it have the usual programming constructs such as ‘While…End’; ‘Case’ and ‘Ifs’; it also, of course, has SQL.

This exercise gave me a chance to use the following programming features of T-SQL:

1. Stored Procedures
2. Tables
3. String manipulation functions
4. ‘While…End’
5. Case statements
6. Temporary tables
7. SQL GROUP BY statements
8. Sub queries

… and probably more.

How the program works

There is no fancy user user-interface. The final program is just one single Stored Procedure called pSolveSudoku. To use it you will need the SQL Analyzer which is the place in SQL Server where SQL queries and stored procedures are run. The example below shows how the stored procedure is used:

The puzzle in Figure 1 is expressed as: As you can see, the stored procedure takes a single parameter which is a string, in which there is a number for each cell. The numbers 1 to 9 are used where the values are already known and 0 is used otherwise. It is a good thing that the SQL Query Analyzer interface allows multiple lines to be used in strings otherwise we would have had to write the entire string on a single line, like this: … which is still okay, but not quite as user-friendly.

When you run the stored procedure you get a table showing all the numbers in their right places (see Figure 2) – a solved Sudoku.

Figure 2: Solution

This information actually comes from a table called tSudoku9x9 which is generated by pSolveSudoku. If you run the following SQL you will get the result of the last puzzle done by the stored procedure. The structure of the table is shown in the table below.

Table 1: The table structure for tSudoku9x9
Column	Data type	Description
R	Integer	Row number
C1	Integer	Column 1
C2	Integer	Column 2
C3	Integer	Column 3
C4	Integer	Column 4
C5	Integer	Column 5
C6	Integer	Column 6
C7	Integer	Column 7
C8	Integer	Column 8
C9	Integer	Column 9

Method

So how does the stored procedure solve the Sudoku?

First let me introduce you to tSudokuData, the most important object in this project. tSudokuData is a table that is populated with all the necessary data which can be queried and updated by stored procedures that automate the task of solving the Sudoku.

tSudokuData contains 81 records, each relating to a cell in the Sudoku. Each record comprises of Location (i.e. row and column number); block information in relation to the cell; ‘Elimination String’ and Current number in the cell.

The ‘Elimination String’ is a special 9-charcter field normally containing ‘123456789’. In the process of solving the puzzle each character is replaced with X when a number has been eliminated from those that can be in the cell. This means that for a cell for which the number is already known the elimination string is ‘XXXXXXXXX’.

The structure of tSudokuData is shown in the table below.

Table 2: The table structure for tSudokuData
Column	Data type	Description
iRow	integer	Row number of the cell (1 to 9)
iCol	integer	column number of the cell (1 to 9)
iVal	integer	the number in the cell 0 for unsolved 1 to 9 for solved
sElim	char(9)	9-character string ‘123456789’, assigned to each cell, in which each character is replaced with X when it has been eliminated from possible numbers that may be used to fill the square
iBlock	integer	Block number (Each block is assigned a number from 1 to 9)
iBRow	integer	Block row (i.e. the row number of the block in the 3X3 grid)
iBCol	integer	Block column (i.e. the column number of the block in the 3X3 grid)
iPos	integer	Within each block the cells are numbered 1 to 9. iPos is the position of the cell within its block.

To populate the table tSudokuData we use the pLoadSudoku Stored Procedure. This does minimal validation on the input string; sets up all the necessary information for each cell, including the elimination string; and assigns values to the cells. Once the table tSudokuData has been created and all the initial information has been inserted into it with pLoadSudokuData, the stage is set for using SQL to solve the Sudoku.

Processing Rules

Sudoku Visual Basic Codes

Most Sudoku fans use a set of rules to place the correct numbers in the cells, in a step-by-step fashion. I can see two kinds of rules:

1. Rules of elimination i.e. finding which number cannot be placed in a cell.
2. Rules of determination i.e. finding which number can be placed in a cell.

Generally I have found that when solving a Sudoku, elimination and determination go hand in hand. A process of elimination often facilitates a process of determination, and vice versa. The ultimate aim is to determine the right number for each cell, but some elimination will have to be done in order to arrive at the right answer.

Elimination

Basic elimination rule:

Sudoku Visual Basic Code Begin With

For each cell, look for any number that already exists in the row, column or block that the cell is contained in. If you find such a number, update the elimination string for that cell.

What you do here is to set a number in the elimination string to ‘X’ once you can tell that the number cannot be placed in the cell because it has already been used in the block, the row or the column that the cell is part of. The Stored procedure for this process is pBasicElimination, and it is shown below: Three things to note: first we have used a while loop to access each cell in the block using the variables @myRow and @myCol; then we have tested for existence numbers 1 to 9 in each row, column or block accordingly using the variable @iCurrentVal; and finally, we have used the replace function to set the numbers that we found in the elimination string to X.

Secondary elimination rule: This rule can be applied if some elimination has already been carried out and it can be stated as: if there is a row, column or block in which two of the cells have both been eliminated down to the same 2 numbers, then those numbers can be eliminated from other cells in the same row column or block.

Figure 3: Two cells eliminated

In the example in Figure 3 we are looking at a block in which 2 cells have been eliminated down to 1 and 3. A third cell has been eliminated down to 1, 3, 7 and 8; and a fourth down to 1, 2, 6 and 9. According to this rule we can eliminate the 1 and 3 in the third and fourth cell.

The stored procedure that deals with this process is pSecondaryElimination which comprises of pSecondaryElimByRow, pSecondaryElimByColumn and pSecondaryElimByBlock. As you can imagine, the three component stored procedures are quite similar, so I will only explain pSecondaryElimRow here. Here we have used temporary tables to hold data as we have gone through the steps required to implement the rule. ‘Exists’, Sub queries and ‘Group By’ have featured in the complex SQL statements. But the code is concise and it is broken down into identifiable stages.

Determination

Basic determination rule: determine for each cell whether there is a number that is the only one that has not been used in the row, column or block to which the cell belongs. If you find such a number then fill the cell with it.

For example, you are looking at a row and you find that it already contains 1, 2, 3, 5,6,7,8 and 9. One cell has not yet been filled. Easy – the missing number is 4, so fill that in.

Since we will be running the Basic elimination Stored procedure first, the elimination string for this cell will be a series of Xs with only one number. i.e. xxx4xxxxx

To fill in all the cells throughout the whole solution, where all the possible candidate numbers have been eliminated down to ‘4’ we use the following SQL: The stored procedure pBasicDetermination, which deals with this rule, is the simplest of all the stored procedures: For most puzzles marked as ‘easy’ in Sudoku puzzle books, the rules discussed so far are normally sufficient to solve them completely, but for harder Sudoku we need more rules.

Rules Of Sudoku Basic

Secondary determination rule: This method is familiar to seasoned Sudoku fans: Take the 3 blocks along the same row. Look for a number n that is contained in 2 of the blocks but not the third. In the block that does not contain the number n; look at the row of cells other than the rows that contain n in the other 2 blocks. If there is only one un-filled cell in that row then it should be filled with the number n.

If there is more than one un-filled cell then look at the column that contains each of the cells, to see whether n as been used. That way you can work out into which of the un-filled cells to place the number n.

Figure 4: Applying the secondary determination rule

In Figure 4, two blocks have the number 8 in rows 1 and 2 respectively, therefore according to the Secondary determination rule, the middle block, which is the one that does not contain 2, should have 8 in the un-filled cell in row 3.

Figure 5: Multiple unfilled cells

Figure 5 shows an example of where more than one unfilled cells have been found. You can see how we have ruled two of them out because ‘3’ has been used in their columns.

This method can also be applied to blocks along the same column, using the same reasoning. The Stored Procedure used for this rule is pSecondaryDetermination and it comprises of pSecondaryDetRowOfBlocks (for blocks in a row) and pSecondaryDetColumnOfBlocks (for column of blocks). Again I will show just one, pSecondaryDetRowOfBlocks: As you can see this is the most complex of all the stored procedures, but it is broken down into stages and comments are provided to explain what we are trying to achieve. Also, notice that the stored procedure requires parameters @number (the number we are testing for) and @blockNumber (the block number of the block that we are processing). This means that this stored procedure will be used in a kind of loop where different values will be passed to it. The passing of values happens in pSecondaryDetermination which is given below:

Putting it all together

Visual Basic Code Functions

The top level stored procedure pSolvesudoku uses the other stored procedures in an iterative manner. These are the steps:

1. Set up the tSudokuTable and load in the input string
2. Find out how many solved cells are in the Sudoku
3. Apply the stored procedures for solving the Sudoku
4. Check the number of solved cells, if still the same, then stop, otherwise go to 3.
5. Indicate whether the Sudoku was completed or not.
6. Display the solution

Conclusion

This has been a fun project. It proves that T-SQL is more versatile than you might imagine, and it only gets better with SQL Server 2005.

This exercise is by no means complete. It can be taken further, by adding more rules so that it can solve harder Sudoku. With some adjustment it can also be converted into a Sudoku Puzzle Generator. It can even be further enhanced and converted to a web service using the new features in SQL Server 2005, but that is another story.

Basic Sudoku Puzzle

Samuel Aina is an IT Consultant working mainly for commercial banks and programming in Visual Basic and SQL Server, among other platforms. He is an MIAP (Member of the Institution of Analysts and Programmers).