6
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – t3chb0t Sep 30 '16 at 6:31
  • \$\begingroup\$ en.wikipedia.org/wiki/Sudoku \$\endgroup\$ – Aaron Allen Sep 30 '16 at 8:59
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – t3chb0t Sep 30 '16 at 9:01
  • \$\begingroup\$ 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. \$\endgroup\$ – Aaron Allen Sep 30 '16 at 9:17
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.