Generating large Sudoku grid in C#

I'm new to C# and am trying to write a program that randomly generates complete Sudoku grid of variable size. I'm able to generate a 25x25 grid in usually less than 10 seconds but I haven't been able to make a 36x36.

This is the method I thought of to create a grid:

• Instantiate structure classes: cells, rows, columns, boxes, and grid.

• Each cell is assigned a random integer.

• A set of functions recurses over each character value (the symbol to be displayed in a cell of the grid) and each box of the grid.

• If a dead end is hit, the state is reverted to the last branch and the next possible path is taken, going through every possible path until a complete grid is created.

```
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace Sudoku
{
class Program
{
// characters used in the grid
public const string valueList = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ?";

static void Main(string[] args)
{
Console.SetWindowSize(150, 60);

Console.SetCursorPosition(0, 0);

// start generating grid
for (int i=0; i { new Grid(4); });
t.Priority = ThreadPriority.Highest;
t.Start();
}
}
}

/**
* Basic building blocks of the grid.
*/
class Cell : IComparable
{
// cell coordinates
public int X;
public int Y;

// Containing groups
public Group Row;
public Group Column;
public Group Box;

// Possible values
public string PossibleValues = Program.valueList;

// Display value
public char Value = 'x';

// Use this to randomize sort order
int I = Grid.Rand.Next();

/**
* Constructor
*/
public Cell (int x, int y, Group row, Group column, Group box, int numValues)
{
X = x;
Y = y;
Ro

Your description of the algorithm used describes the famous backtracking algorithm. This algorithm, by definition, is guaranteed to find a solution, but is terribly slow because it tries all permutations until a solution is found. In order to speed your algorithm up, you should try to solve the grid the way a human would.

The first step is to develop a table of legal values for each cell, rather than just trying any value from the allowed range. This alone will significantly increase the speed of the backtracking solution.

The second step is looking at all possible values in each row, column, and subgrid. If a cell can only have one value, based on the limiting values in the row/column/subgrid, then you have a positive value for that cell, which can be used to reduce the number of allowed values in other cells. You also have a positive value if that cell is the only free cell in one of these subsets to support a specific value.

The third step is slightly more complicated: If any two cells in a row/column/subgrid each can have only two identical values (both cells can have either 2 or 4, for example), then one of those cells will be 2 and the other 4, and you can remove these potential values from all other cells in the subgroup you are examining. The same applies to any N values in N cells ([2, 5], [3, 5], and ([2, 3] or [2, 3, 5]), for example, guarantee that this set of three values will exist in those three cells, and no other cells in the subgroup will have these values).

The fourth step is based on the same principle as the previous point, but is slightly harder to identify. These cells are when any N cells have a block N values that no cells in the subgroup have. For example, if a subgrid only has two cells that allow 2 and 4, but in the current state, placing a 6 or an 8 in one of the cells would not look like a mistake (e.g. the "penciled" values for the cells are [2, 4, 6, 8] and [2, 4, 8], but no other cell in the row/column/subgrid has the values [2, 4]). Identifying these patterns and limiting these cells to supporting [2, 4] can help you limit other cells' potential values, and reduce the numbers checked in your backtracking solution significantly.

Most advanced Sudokus can be solved with just these rules, and if you encounter a legal Sudoku that cannot be solved with these rules, your program will still be significantly faster because it will limit the solution to checking only potential solutions knowing the current state.

StackExchange Code Review Q#141763, answer score: 3