Tworzenie początkowych tablic sudoku

Question

Czy istnieje algorytm lub sposób, w jaki mogę uzyskać początkowe sudoku dla sudoku. Najlepiej ze zdolnością do różnych poziomów trudności?

Answer 1

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

Answer 2

Możesz być zainteresowany tą Sudoku generator.

Answer 3

Zasadniczo istnieją dwa podejścia. W obu musisz mieć 2 solvers, ludzki solver, który używa strategii wykonanych przez człowieka i solver.

Przy pierwszym podejściu generujesz losowe kompletne rozwiązanie i iteracyjnie usuwasz przypadkowe rozwiązania komórkowe. Solver backtrackingu upewni się, że wciąż istnieje tylko jedno rozwiązanie, podczas gdy ludzki solver upewni się, że nadal jest on rozwiązywany przez człowieka i może być również wykorzystany do zmierzenia trudności układanki.

Drugie podejście działa w odwrotny sposób. Najpierw tworzymy pustą planszę i umieszczamy tam przypadkowo 17 rozwiązań komórkowych (w spójny sposób). 17 to najniższa liczba wypełnionych komórek, które generują układankę z unikalnym rozwiązaniem. Teraz algorytm na każdym kroku sprawdza, czy ma już unikalne rozwiązanie, a jeśli nie, dodaje inną (spójnie) wypełnioną komórkę. Jeśli rozwiązanie gwarantuje wyjątkowość rozwiązania, a układanka jest rozwiązywana przez człowieka, a trudność jest poniżej pewnego ograniczenia, algorytm się kończy.

Answer 4

Niedawno otwarty pozyskiwane moim celem generator pokładzie C Sudoku, jeśli jesteś zainteresowany ...

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

To oczywiście wykonane dla iPhone i Mac, ale logika jest przenośna platforma do cokolwiek zdarzy do rozwijania dla.

Answer 5

Rekursywnie sposób na uzyskanie elementów 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

wierzę Devin szuka początkowej konfiguracji sudoku albo Sudoku (z mniej niż 81 komórek wypełnione), która powinna gwarantować 1 lub więcej rozwiązanie istnieje. Losowa konfiguracja komórki N może nie gwarantować rozwiązania.

Sposób, w jaki myślę, to najpierw uzyskać pełne rozwiązanie sudoku, używając go jako bazy (nazwa X) X można przekształcić w dużą ilość innych ważnych rozwiązań sudoku, X1, X2, X3, stosując dowolne liczba następujących przekształceń w dowolnej kolejności: a. obrót b. lustrzana klapka c. zamień całą liczbę x na liczbę y.

Każda z tych baz może zostać użyta do wygenerowania sudoku, losowo odejmując komórki od bazy.

Answer 7

Miałem trochę zabawy w Scali. Możesz usunąć więcej komórek, aby je utrudnić.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) 
}