Creazione delle schede iniziali di sudoku

Question

Esiste un algoritmo o un modo per ottenere i sudoku di stato iniziali per un gioco di sudoku. Preferibilmente con la capacità di avere diversi livelli di difficoltà?

Answer 1

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

Answer 2

Potreste essere interessato a questo Sudoku generator.

Answer 3

Fondamentalmente ci sono due approcci. In entrambi devi avere 2 solvers, un solver umano, che usa strategie eseguibili da un risolutore umano e backtracking.

Con il primo approccio si genera una soluzione completa casuale e si rimuovono iterativamente le soluzioni di celle casuali. Backtracking solver assicurerà che esiste ancora una sola soluzione, mentre il solutore di tipo umano si assicurerà, che è ancora risolvibile da umani e può essere usato anche per misurare la difficoltà del puzzle.

Il secondo approccio funziona in modo opposto. In primo luogo si crea una lavagna vuota e si posizionano casualmente 17 soluzioni di celle (in modo coerente). 17 è il numero di celle piene più basso noto per generare un puzzle con una soluzione unica. Ora l'algoritmo in ogni fase controlla, se ha già una soluzione unica e, in caso contrario, aggiunge un'altra cella (in modo coerente) piena. Se la soluzione garantisce l'unicità della soluzione e il puzzle è risolvibile da un essere umano e la difficoltà è inferiore a qualche limite, l'algoritmo termina.

Answer 4

Recentemente ho open source il mio obiettivo generatore di bordo C Sudoku, se siete interessati ...

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

E 'ovviamente fatto per iPhone e il Mac, ma la logica è portabile su qualsiasi piattaforma vi capita per lo sviluppo per.

Answer 5

Un modo ricorsivo per ottenere elementi di sudoku 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

credo Devin è alla ricerca di una configurazione sudoku iniziale, o un puzzle sudoku (con meno di 81 cellule pieno) che dovrebbe garantire ci sono 1 o più soluzioni. Una configurazione N cell casuale potrebbe non garantire la presenza di una soluzione.

Il modo in cui penso è ottenere una soluzione completa di sudoku, utilizzandola come base (denominarla X) X può essere trasformata in una grande quantità di altre soluzioni di sudoku valide, X1, X2, X3, applicando qualsiasi numero delle seguenti trasformazioni in qualsiasi sequenza: a. rotazione b. mirror flip c. scambia tutto il numero x con il numero y.

Ciascuna di queste basi può quindi essere utilizzata per generare il tuo puzzle di sudoku, deducendo casualmente le celle dalla base.

Answer 7

Ci siamo divertiti con esso in Scala. È possibile rimuovere più celle per renderlo più difficile.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) 
}