14
Có một thuật toán hay cách tôi có thể nhận các câu đố sudoku trạng thái ban đầu cho một trò chơi sudoku. Tốt hơn với khả năng có các mức độ khó khác nhau?Tạo các bảng ban đầu sudoku
A
Trả lời
4
2
Bạn có thể quan tâm Sudoku generator này.
15
Về cơ bản có hai cách tiếp cận. Trong cả hai bạn cần phải có 2 solvers, một người giải quyết nhân loại, trong đó sử dụng các chiến lược có thể thực hiện bởi một người và một người giải mã ngược.
Với cách tiếp cận đầu tiên, bạn tạo ra giải pháp hoàn chỉnh ngẫu nhiên và loại bỏ các giải pháp ô ngẫu nhiên một cách lặp lại. Trình giải mã Backtracking sẽ đảm bảo rằng vẫn chỉ tồn tại một giải pháp, trong khi người giải quyết giống như con người sẽ đảm bảo rằng nó vẫn có thể giải được bằng con người và nó cũng có thể được sử dụng để đo độ khó của câu đố.
Cách tiếp cận thứ hai hoạt động theo kiểu ngược lại. Trước tiên, bạn tạo một bảng trống và đặt ngẫu nhiên 17 giải pháp ô (theo cách nhất quán). 17 là số lượng tế bào được lấp đầy thấp nhất được biết là genrate một câu đố với giải pháp duy nhất. Bây giờ các thuật toán trong mỗi bước kiểm tra, nếu nó đã là một giải pháp duy nhất và nếu không, nó sẽ thêm một ô khác (consitently). Nếu giải pháp đảm bảo giải pháp uniquesness và câu đố được giải quyết bởi một con người và những khó khăn là dưới một số giới hạn, hơn thuật toán chấm dứt.
2
Gần đây tôi đã mở nguồn Mục tiêu phát ban C Sudoku của tôi, nếu bạn quan tâm ...
http://jayfuerstenberg.com/devblog/open-source-code-for-developing-sudoku-for-iphone-and-os-x
Nó rõ ràng là làm cho iPhone và Mac nhưng logic là xách tay để bất cứ điều gì xảy ra nền tảng bạn để phát triển.
0
Cách đệ quy để nhận các phần tử 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);
}
}
}
0
Tôi tin Devin đang tìm kiếm cấu hình sudoku ban đầu hoặc câu đố sudoku (có ít hơn 81 ô) sẽ đảm bảo 1 hoặc nhiều giải pháp tồn tại. Một cấu hình ô N ngẫu nhiên có thể không đảm bảo một giải pháp tồn tại. Cách tôi nghĩ là lần đầu tiên có được một giải pháp sudoku đầy đủ, sử dụng nó làm cơ sở (đặt tên là X) X có thể được chuyển thành một lượng lớn các giải pháp sudoku hợp lệ khác, X1, X2, X3, bằng cách áp dụng bất kỳ số biến đổi sau trong bất kỳ trình tự nào: a. xoay vòng b. gương lật c. hoán đổi tất cả số x với số y.
Mỗi căn cứ sau đó có thể được sử dụng để tạo câu đố sudoku của bạn, bằng cách trừ các ô ngẫu nhiên từ cơ sở.
0
Có một số thú vị với nó ở Scala. Bạn có thể xóa nhiều ô hơn để làm cho nó khó khăn hơn.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)
}
Các vấn đề liên quan
- 1. Đặt chiều rộng bảng ban đầu trong TinyMCE
- 2. CLLocationCài đặt ban đầu
- 3. Cách tạo giá trị ban đầu trong modelform
- 4. Thuật toán máy phát Sudoku
- 5. Giải pháp đệ quy cho trình tạo Sudoku
- 6. Lỗi giải Sudoku
- 7. Phương pháp duy nhất để tạo câu đố sudoku
- 8. Tạo ra một sudoku có khó khăn mong muốn?
- 9. Xác thực biểu mẫu ban đầu bằng các chỉ thị
- 10. detailTextLabel không hiển thị ban đầu
- 11. Giá trị thuộc tính Ban đầu ban đầu để tra cứu EJB
- 12. Shopify Cài đặt ban đầu Snag
- 13. đặt giá trị gia tăng tự động ban đầu cho bảng mysql
- 14. NSString bằng cách loại bỏ các số 0 ban đầu?
- 15. Các hiệu ứng kích thước ban đầu của Java -Xms
- 16. Chuyển ban đầu vào ModelFormSet của Django
- 17. Giá trị ban đầu của một Enum
- 18. iphone uiwebview xem màu trắng ban đầu
- 19. Thuật toán Sudoku trong C#
- 20. Nhận Đường dẫn Ban đầu từ FileStream
- 21. Thứ tự thành phần lớp ban đầu
- 22. Làm thế nào để tìm các thay đổi trong một bảng liên quan đến một trận đấu SQL ban đầu?
- 23. Trình tạo tăng trưởng của NHibernate - không thể tìm nạp giá trị ban đầu
- 24. Cách lấy tên bảng/cột ban đầu khi sử dụng PDO?
- 25. JQuery: Nhận giá trị nhập ban đầu
- 26. Quay lại bảng điều khiển ban đầu ViewController khi đăng xuất
- 27. Biến sao chép thay đổi ban đầu?
- 28. Cách đặt giá trị auto_increment ban đầu bằng doctrine2
- 29. Django, ModelChoiceField() và giá trị ban đầu
- 30. xlrd giá trị ban đầu của ô
"Có". Nhiều câu đố phổ biến có một số phương pháp/giải pháp đã biết. Một chút nghiên cứu sẽ đi một chặng đường dài. –
Có lẽ tôi đã nghiên cứu và không tìm thấy bất cứ điều gì .... là có một chương trình trong C tôi có thể sử dụng? – Devin
Bạn có thể viết một cái và sau đó cho phép người khác sử dụng miễn phí. Hội chợ âm thanh? – Borealid