Création de planches initiales de sudoku

Question

Existe-t-il un algorithme ou une méthode permettant d'obtenir des puzzles de sudoku d'état initial pour un jeu de sudoku? De préférence avec la possibilité d'avoir différents niveaux de difficulté?

Answer 1

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

Answer 2

Vous pourriez être intéressé par cet Sudoku generator.

Answer 3

Fondamentalement, il existe deux approches. Dans les deux vous devez avoir 2 solvers, un solveur humanlike, qui utilise des stratégies exécutables par un humain et un solveur backtracking. Avec la première approche, vous générez une solution complète aléatoire et supprimez itérativement des solutions de cellules aléatoires. Backtracking solver fera en sorte qu'il existe toujours une seule solution, tandis que le solveur de type humain veillera à ce qu'il soit encore résolu par l'homme et il peut également être utilisé pour mesurer la difficulté du puzzle.

La deuxième approche fonctionne de manière opposée. Tout d'abord vous créez un tableau vide et y placez au hasard 17 solutions de cellules (de manière cohérente). 17 est le nombre de cellules pleines le plus bas connu pour générer un puzzle avec une solution unique. Maintenant, l'algorithme dans chaque étape vérifie, s'il a déjà une solution unique et sinon, il ajoute une autre cellule (consitently) remplie. Si la solution garantit une individualité de la solution et que le puzzle est résolu par un humain et que la difficulté est inférieure à une limite, l'algorithme se termine.

Answer 4

J'ai récemment ouvert le code source de mon générateur Objectif C du conseil Sudoku, si vous êtes intéressé ...

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

Il est évidemment fait pour l'iPhone et le Mac, mais la logique est portable à tout ce que la plate-forme vous arrive être en développement pour.

Answer 5

Une manière récursive d'obtenir des éléments de 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

Je crois Devin est à la recherche d'une configuration initiale sudoku, ou un casse-tête sudoku (avec moins de 81 cellules remplies) qui devrait garantir une ou plusieurs solution existe. Une configuration de cellule N aléatoire peut ne pas garantir qu'une solution existe.

La façon dont je pense est d'abord obtenir une solution de sudoku complète, en l'utilisant comme une base (nom X) X peut être transformé en une grande quantité d'autres solutions de sudoku valides, X1, X2, X3, en appliquant nombre de transformations suivantes dans n'importe quelle séquence: a. rotation b. miroir retourné c. échanger tout le nombre x avec le nombre y. Chacune de ces bases peut ensuite être utilisée pour générer votre puzzle de sudoku, en déduisant aléatoirement des cellules de la base.

Answer 7

Je me suis amusé avec ça à Scala. Vous pouvez supprimer plus de cellules pour le rendre plus 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) 
}