sudoku - 创建数独初始板

Question

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

Answer 1

基本上有两种方法。在这两者中，您都需要有 2 个求解器，一个类似于人类的求解器，它使用可由人类执行的策略和一个回溯求解器。

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

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

Answer 2

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

Answer 3

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

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

它显然是为 iPhone 和 Mac 设计的，但逻辑可以移植到你正在开发的任何平台。

Answer 4

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

Answer 5

在 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 6

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

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

然后，这些基础中的每一个都可用于生成您的数独游戏，方法是从基础中随机扣除单元格。

Answer 7

一种获取 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);
        }        
    }
}