Generating large Sudoku grid in C#

Question

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:

1. Instantiate structure classes: cells, rows, columns, boxes, and grid.
2. Each cell is assigned a random integer.
3. 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.
4. 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<4; i++)
 {
 Thread t = new Thread(() => { new Grid(4); });
 t.Priority = ThreadPriority.Highest;
 t.Start();
 }
 }
 }
 /**
 * Basic building blocks of the grid.
 */
 class Cell : IComparable<Cell>
 {
 // 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;
 Row = row;
 Column = column;
 Box = box;
 // assign to groups
 row.AddCell(this);
 column.AddCell(this);
 box.AddCell(this);
 // init possible values
 PossibleValues = PossibleValues.Substring(0, numValues);
 }
 /**
 * Assign a value to this cell while removing it from possible values of related cells
 */
 public void AssignValue(char value)
 {
 if (PossibleValues.Length > 0 && PossibleValues.IndexOf(value) != -1)
 {
 RemoveValueFromGroups(value);
 Value = value;
 }
 }
 /**
 * Remove a value from possible values
 */
 protected void RemoveValue(char value)
 {
 int index = PossibleValues.IndexOf(value);
 // remove value if exists in possible values
 if (index != -1)
 {
 PossibleValues = PossibleValues.Remove(index, 1);
 }
 }
 /**
 * Remove a value from all related group members
 */
 protected void RemoveValueFromGroups (char value)
 {
 for (int i=0; i<Row.Cells.Length; i++)
 {
 Row.Cells[i].RemoveValue(value);
 Column.Cells[i].RemoveValue(value);
 Box.Cells[i].RemoveValue(value);
 }
 }
 /**
 * Used to sort cells randomly using their assigned RNG value I
 */
 public int CompareTo(Cell c)
 {
 if (c == null) return 0;
 return I.CompareTo(c.I);
 }
 /**
 * Regenerate the RNG value
 */
 public void ReseedRng()
 {
 I = Grid.Rand.Next();
 }
 }
 /**
 * A class that holds the cells. Can be rows, columns, or boxes
 */
 class Group
 {
 public Cell[] Cells;
 protected int Index = 0;
 /**
 * Constructor
 */
 public Group (int numCells)
 {
 Cells = new Cell[numCells];
 }
 /**
 * Add a cell to the group
 */
 public void AddCell (Cell cell)
 {
 Cells[Index++] = cell;
 }
 /**
 * Get a sorted set of all cells that can potential have the given value
 */
 public SortedSet<Cell> GetCandidates (char value)
 {
 SortedSet<Cell> candidates = new SortedSet<Cell>();
 // Add eligible cells
 foreach (Cell cell in Cells)
 {
 if (cell.Value == 'x' && cell.PossibleValues.Contains(value))
 {
 candidates.Add(cell);
 }
 }
 return candidates;
 }
 }
 /**
 * Class that represents the sudoku square and all it's parts
 */
 class Grid
 {
 //static Grid Instance;
 string PossibleValues = Program.valueList;
 public int BoxSideLength;
 public static Random Rand = new Random();
 public Group[] Rows;
 public Group[] Columns;
 public Group[] Boxes;
 public Cell[] Cells;
 protected static bool CompletedGrid = false;
 /**
 * Constructor
 */
 public Grid (int boxSideLength)
 {
 int sideLength = boxSideLength * boxSideLength;
 BoxSideLength = boxSideLength;
 PossibleValues = PossibleValues.Substring(0, sideLength);
 Rows = new Group[sideLength];
 Columns = new Group[sideLength];
 Boxes = new Group[sideLength];
 // instantiate the groups
 for (int i=0; i<sideLength; i++)
 {
 Rows[i] = new Group(sideLength);
 Columns[i] = new Group(sideLength);
 Boxes[i] = new Group(sideLength);
 }
 Cells = new Cell[sideLength * sideLength];
 // instantiate the cells
 for (int y=0; y<sideLength; y++)
 {
 for (int x=0; x<sideLength; x++)
 {
 int boxIndex = (x / boxSideLength) + (y / boxSideLength) * boxSideLength;
 Cells[x + y * sideLength] = new Cell(x, y, Rows[y], Columns[x], Boxes[boxIndex], sideLength);
 }
 }
 // start building the grid
 // Assign the cell values
 while (!PopulateChar(PossibleValues[0]))
 {
 // reset Rng if complete failure occurs
 foreach (Cell cell in Cells)
 {
 cell.ReseedRng();
 }
 }
 // first completed grid
 if (!CompletedGrid)
 {
 CompletedGrid = true;
 Draw();
 Console.ReadLine();
 }
 }
 /** 
 * Used to recursively feed values into the AssignValues method
 */
 protected bool PopulateChar(char value)
 {
 //Console.SetCursorPosition(0, 0);
 //Draw();
 // check for completed grid, end processing
 if (CompletedGrid)
 {
 return true;
 }
 return AssignValues(Boxes[0], value);
 }
 /**
 * Used to recursively assign the given value to a cell in each box group
 */
 protected bool AssignValues(Group box, char value)
 {
 var candidates = box.GetCandidates(value);
 if (candidates.Count > 0)
 {
 foreach (Cell cell in candidates)
 {
 // check for completed grid, end processing
 if (CompletedGrid)
 {
 return true;
 }
 // save current state of grid
 State[] states = new State[Cells.Length];
 for (int i=0; i<Cells.Length; i++)
 {
 states[i] = new State(Cells[i].Value, Cells[i].PossibleValues);
 }
 cell.AssignValue(value);
 // determine if this cell will cause the next box to error
 int index = Array.IndexOf(Boxes, box);
 int gridRowIndex = index / BoxSideLength;
 int gridColIndex = index % BoxSideLength;
 bool causesError = false;
 for (int i = index + 1; i < Boxes.Length; i++)
 {
 if (/*i > BoxSideLength * 2 &&*/ gridRowIndex != i / BoxSideLength || gridColIndex != i % BoxSideLength) continue;
 bool hasFreeCell = false;
 foreach (Cell testCell in Boxes[i].Cells)
 {
 if (testCell.PossibleValues.Contains(value))
 {
 hasFreeCell = true;
 break;
 }
 }
 if (!hasFreeCell)
 {
 causesError = true;
 break;
 }
 }
 // move on to next box if no error
 if (!causesError)
 {
 int nextBoxIndex = index + 1;
 if (nextBoxIndex == Boxes.Length)
 {
 // start assigning next character
 int indexOfNextChar = PossibleValues.IndexOf(value) + 1;
 // Check for grid completion
 if (indexOfNextChar == PossibleValues.Length) return true;
 // move on to next char
 if (PopulateChar(PossibleValues[indexOfNextChar])) return true;
 }
 else
 {
 // recurse through next box
 if (AssignValues(Boxes[nextBoxIndex], value)) return true;
 }
 }
 // undo changes made in this recursion layer
 for (int i = 0; i < Cells.Length; i++)
 {
 Cells[i].Value = states[i].Value;
 Cells[i].PossibleValues = states[i].PossibleValues;
 }
 }
 }
 return false; // no viable options, go back to previous box or previous character
 }
 /**
 * Output the grid to console
 */
 public void Draw()
 {
 int rowCounter = 0;
 foreach (Group row in Rows)
 {
 StringBuilder rowString = new StringBuilder();
 foreach (Cell cell in row.Cells)
 {
 rowString.Append(cell.Value);
 rowString.Append(' ', 2);
 }
 rowCounter++;
 if (rowCounter == BoxSideLength)
 {
 rowCounter = 0;
 Console.WriteLine(rowString.Append('\n').Append('-', Rows.Length*3));
 }
 else
 Console.WriteLine(rowString + "\n");
 }
 }
 }
}
/**
 * Used for persisting a cell's state
 */
struct State
{
 public char Value;
 public string PossibleValues;
 public State(char value, string possibleValues)
 {
 Value = value;
 PossibleValues = possibleValues;
 }
}

The Grid constructor is passed an integer that is the square root of a side length of the grid, so 5 for a 25x25 grid.

Any tips on how to generate 36x36 and larger grids within a reasonable amount of time?

• t3chb0t: Could you explain the rules for the sudoku grind and what are the cells, rows, columns, boxes, and grid for? It looks like have a lot of redundancy there.
• Aaron Allen: en.wikipedia.org/wiki/Sudoku
• t3chb0t: I know ;-) I meant your implementation because when I run it it prints some alpha-numeric strings and I didn't know how to interpet them ;-] maybe you could explain the output too.
• Aaron Allen: The output is the grid but only the horizontal lines are shown. For sizes greater than 9x9, alpha chars are used in addition to numbers.

Answer 1

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.