Creating sudoku initial boards

Question

Is there an algorithm or way I can get initial state sudoku puzzles for a sudoku game. Preferably with the ability to have different levels of difficulty?

Answer 1

Had some fun with it in Scala. You can remove more cells to make it more difficult.Scala

import scala.collection.mutable.Set
import scala.util.Random

object SudokuApp extends App {

  def printout(header: String, p: Array[Array[Int]]) {
    println(s"--- $header ---")
    p.map { row => row.map(print); println("") }
  }

  // create a possible solution
  val puzzle = new Sudoku(Array.fill(9, 9)(0)).a

  // create a puzzle by remove a number of cells
  remove(puzzle, 60);

  printout("puzzle", puzzle)

  // solve the puzzle
  printout("solution", new Sudoku(puzzle).a)

  def remove(a: Array[Array[Int]], count: Int) {
    val rs = Random.shuffle(List.range(0, 81))
    for (i <- 0 until count)
      a(rs(i) / 9)(rs(i) % 9) = 0
  }
}

class Sudoku(val a: Array[Array[Int]]) {
  val r = Array.fill(9)(Set[Int]())
  val c = Array.fill(9)(Set[Int]())
  val z = Array.fill(3, 3)(Set[Int]())

  for (x <- 0 to 8; y <- 0 to 8)
    if (a(x)(y) != 0)
      setExist(a(x)(y), x, y)

  def setExist(v: Int, x: Int, y: Int) {
    r(x) += v
    c(y) += v
    z(x / 3)(y / 3) += v
  }

  def fill(x: Int, y: Int): Boolean = {
    if (a(x)(y) == 0) {
      val candidates = Set() ++ (1 to 9) -- r(x) -- c(y) -- z(x / 3)(y / 3)

      def current(): Boolean = {
        if (candidates.isEmpty)
          false
        else {
          val v = Random.shuffle(candidates.toList).iterator.next
          candidates -= v
          a(x)(y) = v
          setExist(v, x, y)
          val good = if (y < 8) fill(x, y + 1) else if (x < 8) fill(x + 1, 0) else true
          if (good)
            true
          else {
            a(x)(y) = 0
            r(x) -= v
            c(y) -= v
            z(x / 3)(y / 3) -= v
            current
          }
        }
      }

      current
    }
    else if (y < 8) fill(x, y + 1) else if (x < 8) fill(x + 1, 0) else true
  }

  fill(0, 0)
}

Answer 2

A recursively way to get 9x9 sudoku elements.

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace SP3.Sudoku
{
    static class Program
    {       
        [STAThread]
        static void Main()
        {
            Application.EnableVisualStyles();
            Application.SetCompatibleTextRenderingDefault(false);
            Application.Run(new Sudoku());
        }
    }

    public partial class Sudoku : Form
    {
        private System.Windows.Forms.Button btGenerate;
        private System.Windows.Forms.Button btClear;
        private System.ComponentModel.BackgroundWorker bw;
        private System.Windows.Forms.Button btTestOk;
        private delegate void setCellValue(int cellIndex, int cellValue);


        public Sudoku()
        {
            InitializeComponent();
            createControls();
        }

        public List<int> SudokuControlsValues
        {
            get
            {
                List<int> result = new List<int>(81);

                for (int i = 0; i < 9; i++)
                    for (int j = 0; j < 9; j++)
                        result.Add((int)sudokuControlsValues[j + (i * 9)].Value);

                return result;
            }
            set
            {
                List<int> result = value as List<int>;
                for (int i = 0; i < result.Count; i++)
                    sudokuControlsValues[i].Value = result[i];
            }
        }

        private void InitializeComponent()
        {
            this.btGenerate = new System.Windows.Forms.Button();
            this.btClear = new System.Windows.Forms.Button();
            this.bw = new System.ComponentModel.BackgroundWorker();
            this.btTestOk = new System.Windows.Forms.Button();
            this.SuspendLayout();
            // 
            // btGenerate
            // 
            this.btGenerate.Location = new System.Drawing.Point(534, 458);
            this.btGenerate.Name = "btGenerate";
            this.btGenerate.Size = new System.Drawing.Size(75, 23);
            this.btGenerate.TabIndex = 1;
            this.btGenerate.Text = "Generate";
            this.btGenerate.UseVisualStyleBackColor = true;
            this.btGenerate.Click += new System.EventHandler(this.btGenerate_Click);
            // 
            // btClear
            // 
            this.btClear.Location = new System.Drawing.Point(453, 458);
            this.btClear.Name = "btClear";
            this.btClear.Size = new System.Drawing.Size(75, 23);
            this.btClear.TabIndex = 3;
            this.btClear.Text = "Clear";
            this.btClear.UseVisualStyleBackColor = true;
            this.btClear.Click += new System.EventHandler(this.btClear_Click);
            // 
            // bw
            // 
            this.bw.WorkerReportsProgress = true;
            this.bw.WorkerSupportsCancellation = true;
            this.bw.DoWork += new System.ComponentModel.DoWorkEventHandler(this.bw_DoWork);
            // 
            // btTestOk
            // 
            this.btTestOk.Location = new System.Drawing.Point(372, 458);
            this.btTestOk.Name = "btTestOk";
            this.btTestOk.Size = new System.Drawing.Size(75, 23);
            this.btTestOk.TabIndex = 4;
            this.btTestOk.Text = "Test";
            this.btTestOk.UseVisualStyleBackColor = true;
            this.btTestOk.Click += new System.EventHandler(this.btTestOk_Click);
            // 
            // Sudoku
            // 
            this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
            this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
            this.BackColor = System.Drawing.SystemColors.ControlDark;
            this.ClientSize = new System.Drawing.Size(624, 493);
            this.Controls.Add(this.btTestOk);
            this.Controls.Add(this.btClear);
            this.Controls.Add(this.btGenerate);
            this.FormBorderStyle = System.Windows.Forms.FormBorderStyle.FixedSingle;
            this.MaximizeBox = false;
            this.MinimizeBox = false;
            this.Name = "Sudoku";
            this.ShowIcon = false;
            this.StartPosition = System.Windows.Forms.FormStartPosition.CenterScreen;
            this.Text = "Sudoku generator";
            this.ResumeLayout(false);

        }

        private void btGenerate_Click(object sender, System.EventArgs e)
        {
            bw.RunWorkerAsync();
        }

        private void btClear_Click(object sender, System.EventArgs e)
        {
            createControls();
        }

        private void createControls()
        {
            createControls(new Size(33, 10), new Size(3, 5), new Size(15, 30), new Size(15, 30), false, true);
        }

        private void clearControls()
        {
            if (sudokuControlsValues == null)
                return;

            foreach (NumericUpDown item in sudokuControlsValues)
            {
                if (item != null)
                {
                    this.Controls.Remove(item);
                    item.Dispose();
                }
            }

            sudokuControlsValues = null;
        }

        private void createControls(Size size, Size itemSeparation, Size startMargin, Size groupSeparation, bool AddRandomValue, bool addTest)
        {
            clearControls();

            sudokuControlsValues = new List<NumericUpDown>(81);

            int
               grSeparationW = 0,
               grSeparationH = 0;

            for (int i = 0; i < 9; i++)
            {
                for (int j = 0; j < 9; j++)
                {
                    NumericUpDown nud = new NumericUpDown();

                    // In order to debug easier save indexes values within the tag property and assing click event.
                    if (addTest)
                    {
                        nud.Tag = new int[2] { i, j };
                        nud.Click += nud_Click;
                    }

                    // Values
                    nud.Maximum = 9;
                    nud.Minimum = 0;
                    nud.TextAlign = HorizontalAlignment.Center;
                    nud.Size = size;

                    // Location
                    nud.Location = new Point(
                        (j * (nud.Width + itemSeparation.Width) + grSeparationW) + startMargin.Width,
                        (i * (nud.Height + itemSeparation.Height) + grSeparationH) + +startMargin.Height);

                    if (AddRandomValue)
                        nud.Value = (decimal)new Random(DateTime.Now.Millisecond).Next(1, 10);

                    Controls.Add(nud);

                    // Box separation
                    if (j % 3 == 2)
                        grSeparationW += groupSeparation.Width;

                    // Matrix reference
                    sudokuControlsValues.Add(nud);
                }

                grSeparationW = 0;

                if (i % 3 == 2)
                    grSeparationH += groupSeparation.Height;
            }
        }

        private void nud_Click(object sender, EventArgs e)
        {
            NumericUpDown ctr = sender as NumericUpDown;
            Color backColr = Color.FromName(ctr.BackColor.Name);
            Color fontColr = Color.FromName(ctr.ForeColor.Name);

            ctr.BackColor = fontColr;
            ctr.ForeColor = backColr;
            int[] indexes = (int[])ctr.Tag;

            // Get elements
            List<int> elements = SudokuControlsValues;

            List<int>
                row = readRow(indexes[0], elements),
                column = readColumn(indexes[1], elements),
                square = readSquare(indexes[0], indexes[1], elements);

            StringBuilder message = new StringBuilder();
            message.AppendLine("VALUE => {0}\n");
            message.AppendLine("ROW INDEX => {1}");
            message.AppendLine("COLUMN INDEX => {2}");
            message.AppendLine("ROW => {3}");
            message.AppendLine("COLUMN => {4}");
            message.AppendLine("SQUARE => {5}");
            message.AppendLine("ROW TIMES => {6}");
            message.AppendLine("COLUMN TIMES => {7}");
            message.AppendLine("SQUARE TIMES => {8}");

            MessageBox.Show(
                string.Format(message.ToString(),

                new object[] 
                { 
                    ctr.Value,
                    indexes[0], // Row
                    indexes[1], // Column                    
                    string.Join(" ", row), 
                    string.Join(" ", column), 
                    string.Join(" ", square),
                    row.Count(n=>n==(int)ctr.Value),
                    column.Count(n=>n==(int)ctr.Value),
                    square.Count(n=>n==(int)ctr.Value),
                }));

            ctr.BackColor = backColr;
            ctr.ForeColor = fontColr;
        }

        private List<int> readRow(int index, List<int> elements)
        {
            List<int> result = new List<int>();

            for (int i = 9 * index; i < (9 * index) + 9; i++)
                result.Add(elements[i]);

            return result;
        }

        private List<int> readColumn(int index, List<int> elements)
        {
            List<int> result = new List<int>();

            for (int i = index; i < elements.Count; i += 9)
                result.Add(elements[i]);

            return result;
        }

        private List<int> readSquare(int rowIndex, int columnIndex, List<int> elements)
        {
            List<int> r = new List<int>();

            // int root = (int)(Math.Sqrt((double)elements.Count));
            int root = 9;
            rowIndex = rowIndex - rowIndex % 3;
            columnIndex = columnIndex - columnIndex % 3;

            for (int i = rowIndex; i < rowIndex + 3; i++)
                for (int j = columnIndex; j < columnIndex + 3; j++)
                    r.Add(elements[(i * root) + j]);

            return r;
        }

        private void bw_DoWork(object sender, System.ComponentModel.DoWorkEventArgs e)
        {
            List<int> data = new List<int>();
            List<int> remainingNums = new List<int>();
            for (int i = 0; i < 9; i++)
                for (int j = 1; j < 10; j++)
                {
                    remainingNums.Add(j);
                    data.Add(0);
                }

            populateRecursive(data, 0, remainingNums, e);
        }

        private bool populateRecursive(List<int> data, int cellIdx, List<int> remainingNums, System.ComponentModel.DoWorkEventArgs e)
        {
            if (remainingNums.Count < 1)
                return true;

            List<int> options = calcNumberOptions(data, cellIdx, remainingNums);
            options = shuffle(options);

            for (int i = 0; i < options.Count; i++)
            {
                int num = options[i];

                remainingNums.Remove(options[i]);
                data[cellIdx] = num;
                setCell(cellIdx, num);

                if (populateRecursive(data, cellIdx + 1, remainingNums, e))
                    return true;

                data[cellIdx] = 0;
                remainingNums.Add(num);
            }

            return false;
        }

        private void setCell(int cellIdx, int value)
        {
            NumericUpDown nud = sudokuControlsValues[cellIdx] as NumericUpDown;

            if (nud.InvokeRequired)
            {
                setCellValue d = new setCellValue(setCell);
                this.Invoke(d, new object[] { cellIdx, value });
            }
            else
                nud.Value = value;
        }

        private List<int> shuffle(List<int> elements)
        {
            if (elements.Count < 1)
                return elements;

            List<int> bse = new List<int>(elements);
            List<int> res = new List<int>();
            int indexTaken = -1;

            do
            {
                indexTaken = new Random((int)DateTime.Now.Ticks).Next(bse.Count);
                res.Add(bse[indexTaken]);
                bse.RemoveAt(indexTaken);
            }
            while (bse.Count > 0);

            return res;
        }

        private List<int> cellIndexToCellParIndex(int cellIndex)
        {
            int
               rowIndex = (int)Math.Floor(cellIndex / 9f),
               colIndex = cellIndex - rowIndex * 9;

            return new List<int> { rowIndex, colIndex };
        }

        private List<int> calcNumberOptions(List<int> data, int cellIndex, List<int> remainingNums)
        {
            List<int> result = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
            List<int> cellParIndex = cellIndexToCellParIndex(cellIndex);

            int
                rowIndex = cellParIndex[0],
                colIndex = cellParIndex[1];

            List<int> readAllElements = new List<int>();
            readAllElements.AddRange(readRow(rowIndex, data));
            readAllElements.AddRange(readColumn(colIndex, data));
            readAllElements.AddRange(readSquare(rowIndex, colIndex, data));
            readAllElements = readAllElements.Distinct().ToList();
            readAllElements.ForEach(n => result.Remove(n));

            return result;
        }         

        private List<NumericUpDown> sudokuControlsValues = new List<NumericUpDown>(81);       

        private void btTestOk_Click(object sender, EventArgs e)
        {
            List<int> elements = SudokuControlsValues;
            string result = "OK!";

            for (int i = 0; i < elements.Count; i++)
            {                
                List<int> cellIndexPar = cellIndexToCellParIndex(i);
                int
                    currentElement = elements[i],
                    rowIndex = cellIndexPar[0],
                    cellIndex = cellIndexPar[1];

                List<int>
                    row = readRow(rowIndex, elements),
                    col = readColumn(cellIndex, elements),
                    sqr = readSquare(rowIndex, cellIndex, elements);

                if (row.Count(n => n == currentElement) > 1 ||
                    col.Count(n => n == currentElement) > 1 ||
                    sqr.Count(n => n == currentElement) > 1)
                {
                    result = "KO...";
                    break;
                }
            }

            MessageBox.Show(result);
        }        
    }
}

Answer 3

Basically there are two approaches. In both you need to have 2 solvers, a humanlike solver, which uses strategies performable by a human and a backtracking solver.

With the first approach you generate a random complete solution and iteratively remove random cells solutions. Backtracking solver will make sure, that there still exist only one solution, while the human-like solver will make sure, that its still solvable by human and it can be also used to measure the difficulty of the puzzle.

The second approach works in an opposite fashion. Firstly you create an empty board and place there randomly 17 cell solutions (in a consistent manner). 17 is the lowest filled cell count known to genrate a puzzle with unique solution. Now the algorithm in every step checks, if it has already an unique solution and if not, it adds another (consitently) filled cell. If the solution guarantees solution uniquesness and the puzzle is solvable by a human and the difficulty is below some limit, than the algorithm terminates.

Answer 4

I believe Devin is looking for a initial sudoku configuration, or a sudoku puzzle (with less than 81 cells filled) which should guarantee 1 or more solution exists. A random N cell configuration may not guarantee a solution exists.

The way I think of is first obtain a full sudoku solution, using it as a base (name it X) X can be transformed into large amount of other valid sudoku solutions, X1, X2, X3, by applying any number of following transformations in any sequence: a. rotation b. mirror flip c. swap all number x with number y.

Each of these bases then can be used to generate your sudoku puzzle, by randomly deducting cells from the base.

Answer 5

You might be interested in this Sudoku generator.

Answer 6

I recently open sourced my Objective C Sudoku board generator, if you're interested...

http://jayfuerstenberg.com/devblog/open-source-code-for-developing-sudoku-for-iphone-and-os-x

It's obviously made for iPhone and the Mac but the logic is portable to whatever platform you happen to be developing for.