Creando tablas iniciales de sudoku

Question

¿Hay algún algoritmo o forma en que pueda obtener rompecabezas de sudoku de estado inicial para un juego de sudoku? Preferiblemente con la capacidad de tener diferentes niveles de dificultad?

Answer 1

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

Answer 2

Usted puede estar interesado en este Sudoku generator.

Answer 3

Básicamente hay dos enfoques. En ambos necesitas tener 2 solvers, un solucionador similar al humano, que usa estrategias ejecutables por un humano y un solucionador de retroceso.

Con el primer enfoque genera una solución aleatoria completa y elimina iterativamente soluciones de celdas aleatorias. El solucionador de retroceso se asegurará de que todavía exista una sola solución, mientras que el solucionador humano se asegurará de que todavía pueda ser solucionado por el humano y también se puede usar para medir la dificultad del rompecabezas.

El segundo enfoque funciona de manera opuesta. Primero creas un tablero vacío y colocas al azar 17 soluciones celulares (de manera consistente). 17 es el recuento de células rellenas más bajo conocido para generar un rompecabezas con una solución única. Ahora el algoritmo en cada paso comprueba, si ya tiene una solución única y si no, agrega otra celda (consitentemente) llena. Si la solución garantiza la singularidad de la solución y el rompecabezas es solucionable por un humano y la dificultad está por debajo de un límite, entonces el algoritmo termina.

Answer 4

Recientemente código abierto mi generador Junta C Sudoku objetivo, si está interesado ...

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

Es obvio que es hecha para el iPhone y el Mac, pero la lógica es portable a cualquier plataforma le sucede estar desarrollando para.

Answer 5

Una manera recursiva de obtener elementos de sudoku de 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

I creen Devin está buscando una configuración sudoku inicial, o un rompecabezas sudoku (con menos de 81 celdas llenas), que debe garantizar existe 1 o más solución. Una configuración aleatoria de N celdas puede no garantizar que exista una solución.

La forma en que pienso es primero obtener una solución de sudoku completa, usándola como base (llámela X) X puede transformarse en una gran cantidad de otras soluciones de sudoku válidas, X1, X2, X3, aplicando cualquier número de siguientes transformaciones en cualquier secuencia: a. rotación b. cambio de perspectiva c. intercambia todo el número x con el número y.

Cada una de estas bases se puede utilizar para generar su sudoku, deduciendo aleatoriamente las celdas de la base.

Answer 7

Pasamos un buen rato en Scala. Puede eliminar más celdas para hacerlo más difícil. Escala

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) 
}