创建数独初始板

Question

有没有一种算法或方法可以让我获得数独游戏的初始状态数独谜题。最好有不同难度级别的能力？

Answer 1

您可能对此数独生成器感兴趣。

Answer 2

我最近开源了我的 Objective C 数独板生成器，如果您有兴趣...

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

显然是制作的适用于 iPhone 和 Mac，但逻辑可以移植到您正在开发的任何平台。

Answer 3

我相信 Devin 正在寻找一个初始数独配置，或者一个数独谜题（填充的单元格少于 81 个），它应该保证存在 1 个或多个解决方案。随机的 N 个单元配置可能无法保证解的存在。

我想到的方法是首先获得一个完整的数独解决方案，将其用作基础（将其命名为X）
通过按任意顺序应用任意数量的以下变换，X 可以变换为大量其他有效的数独解 X1、X2、X3：
一个。旋转
b.镜面翻转
c.将所有数字 x 与数字 y 交换。

然后，通过从基数中随机扣除单元格，每个基数都可以用于生成数独谜题。

Answer 4

在 Scala 中玩得很开心。您可以删除更多单元格以使其变得更加困难。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 5

一种获取 9x9 数独元素的递归方法。

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 6

基本上有两种方法。在这两种情况下，您都需要有 2 个求解器，一个类似人类的求解器，它使用可由人类和回溯求解器。

使用第一种方法，您可以生成随机完整解决方案并迭代删除随机单元解决方案。回溯求解器将确保仍然只存在一种解决方案，而类人求解器将确保它仍然可以由人类解决，并且还可以用于衡量难题的难度。

第二种方法的工作方式相反。首先，您创建一个空板并随机放置 17 个细胞溶液（以一致的方式）。 17 是已知可生成具有独特解决方案的谜题的最低填充单元数。现在，每个步骤中的算法都会检查是否已经有唯一的解决方案，如果没有，则添加另一个（持续）填充的单元格。如果解决方案保证解决方案的唯一性并且难题可由人类解决并且难度低于某个限制，则算法终止。

Answer 7

http://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf