**Generating a Sudoku Grid**
In my mind, the primary requirement for a generated Sudoku grid is that it should be random; every time someone requests a new game, the probability of getting a unique grid should be very high. To achieve this the application uses a random number generator to populate the grid. After generating a number for each cell, the program has to check that the grid as generated so far is a valid Sudoku grid; if not, you have to backtrack. This is why you need the two variables shown here:

```
Dictionary<string, List<int>[,]> s = new
Dictionary<string, List<int>[,]>();
int[,] grid = new int[9, 9];
```

In the preceding code, one variable is a two-dimensional integer array called

grid. This variable stores the Sudoku grid generated so far. The other variable, named

s, is a dictionary in which each item is a two-dimensional integer array. Each step in the generation process stores the partially completed grid. Then, when the generation process needs to backtrack, it can use the dictionary to retrieve the last valid partial grid generated.

```
// initialise the state to contain 1 to 9 in each
// cell
List<int>[,] gridCopy = Initialise();
bool backTracking = false;
List<int> used = new List<int>();
List<int> backTracked = new List<int>();
```

In the code snippet above,

gridCopy is a two-dimensional array of a list that can only contain integers. The list comes from the generic classes in the .net framework 2.0. Think of a List as a two-dimensional ArrayList where only integers are allowed to be stored. Each cell in

gridCopy represents a cell in the Sudoku grid. Initially, you fill each cell in

gridCopy with the allowable numbers 1 to 9, because at the start of the algorithm, any of those numbers can be assigned to any cell.

The code also declares a flag named

backTracking which lets you know whether or not backtracking is required. Finally, we declare the variable

used, which stores the numbers the process has attempted to use to fill a cell. Because the algorithm chooses a number between 1 and 9 at random, the

used list prevents it from attempting to use a number that's already been tried unsuccessfully.

```
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
used = new List<int>();
if (backTracking)
{
i--;
j = 0;
bool getSucceeded =
s.TryGetValue(i.ToString() +
j.ToString(),out gridCopy);
for (int k = i; k < 9; k++)
{
for (int z = 0; z < 9; z++)
{
grid[k, z] = 0;
}
}
```

In backtracking mode, the code steps back one row (by decrementing the row loop counter

i by 1 and resetting the column loop counter to zero). Moreover, it retrieves the last valid grid from the dictionary. The code continues:

```
}
bool assigned = false;
//try to assign a number to this cell.
List<int>[,] thisCopy = Copy(gridCopy);
Random rnd = new Random();
while (!assigned && used.Count < 9)
{
bool canUseValue = false;
int sudokuValue = rnd.Next(1, 10);
//can we use this value
while (used.Contains( sudokuValue) )
{
sudokuValue = rnd.Next(1, 10);
}
canUseValue = Check(i, j, sudokuValue,
grid);
```

The preceding code randomly picks an integer between 1 and 9, inclusive, and then checks whether or not that number can work in that position. The code checks by applying the three rules that govern number placement in a Sudoku grid. If the selected number is compliant with the rules, then it's a successful match. If not, the code keeps on trying different numbers until all possible numbers (1-9) are exhausted, in which case it has to backtrack.

```
if (canUseValue)
{
grid[i, j] = sudokuValue;
if (s.ContainsKey(i.ToString() +
j.ToString()))
{
s.Remove(i.ToString() +
j.ToString());
}
s.Add(i.ToString() + j.ToString(),
thisCopy);
gridCopy = thisCopy;
assigned = true;
backTracking = false;
}
else
{
if (!used.Contains(sudokuValue))
{
used.Add(sudokuValue);
}
}
}
if (!assigned)
{
backTracking = true;
}
}
}
return grid;
}
```

As you may have noticed, I used the collection classes in System.Collections.Generic extensively in the backtracking algorithm to generate the Sudoku grid. The generic classes deliver greatly improved performance because they eliminate the boxing and unboxing that's necessary with the non-generic versions. I noticed more than 100% improvement when I switched to the generic classes. The end result of the Generate method is a valid Sudokku grid containing numbers 1 to 9 in all the 81 cells.

Observant readers probably noticed that the generator code always backtracks one row whenever it proves to be impossible to generate a valid Sudoku grid using the current row numbers. One way to improve the algorithm is make it a little bit more intelligent and backtrack by just one cell.