数独生成算法 [英] Sudoku generator algorithm

问题描述

我做了算法来生成数独游戏，但它是非常低效的。每一个难题需要几分钟来产生。所以，现在我想以最佳的方式再写一遍。但我遇到了一些问题，我需要帮助。

1. 有两种aproaches，先从空的网格，并添加数字，然后检查是否是可解的。第二种方法是创建完整的有效的网格，所有81个数字，然后取出，直到我们很高兴与剩余数的数量，它仍然是可以解决的。

首先，我用第一种方法，但现在我会，因为我觉得这是更有效的（我们开始与保证是可解的谜题有效），使用第二个。我是正确的，第二种方法比较好？

1. 当我试图生成完全填充的网格我遇到的困难。我的算法是：

   
   
   
   
   
   • 设置考生每个细胞。 Initialy它们是数字1到9。
   
   
   • 选择随机细胞没有价值。
   
   
   • 从该小区随机选择候选人，并将其指定为单元格的值。其他候选人被丢弃。
   
   
   • 现在，对应于已分配单元每一行，电池和方形，我从这些候选人中删除单元格的值，因此每个数字都是独特的行/列/平方米
   
   
   • 重复
   
   

这方法保证随机电网无重复号。然而，大多数的时候，当我不打破安置冲突运行任何规则 - 就像，所有候选人都被删除等，我需要重新开始空单元格。是否有填充数字整个电网没有打破配售规则，还随机数更优雅/有效的方式？

感谢您。

< DIV CLASS =h2_lin>解决方案

让你看着现有的算法和/或代码？

检查出的 http://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf 一个算法描述，和彼得·诺维格的在的http://norvig.com/sudoku.html 。

有一些实现了有Python编写的。到目前为止，我从来没有见过一个发布的C＃解决方案。

祝你好运！

I made an algorithm to generate sudokus, but it was terribly inefficient. Each puzzle took minutes to generate. So now I am trying to write it again in optimal way. But I am experiencing some problems I need help with.

1. There are two aproaches, start with blank grid and add numbers, then check if it is solvable. Second approach is to create full valid grid with all 81 numbers and then remove until we are happy with number of remaining numbers and it is still solvable.

First I used first approach but now I am going to use second because I think it is more effective (we are starting with valid puzzle which is guaranteed to be solvable). I am right that second approach is better?

1. When I am trying to generate full populated grid I am running into difficulties. My algorithm is:

   • Set candidates for each cells. Initialy they are numbers 1 through 9.
   • Pick random cell without value.
   • Select random candidate from that cell and assign it as cell value. Other candidates are discarded.
   • Now for each row, cell and square corresponding to assigned cell I remove value of cell from these candidates, so each number is unique in a row/column/square
   • Repeat

This technique guarantees random grid without duplicate numbers. However, most of times, when I do not break any rules of placement a run to conflict - like empty cells where all candidates have been removed etc and I need to start over. Is there more elegant/efficient way to filling entire grid with numbers without breaking rules of placement and still random numbers?

Thank you.

解决方案

Have you looked at existing algorithms and/or code?

Check out http://www.sudokuwiki.org/Sudoku_Creation_and_Grading.pdf for an algorithmic description, and Peter Norvig's article at http://norvig.com/sudoku.html.

There are some implementations out there in Python. So far I've never seen a published C# solution.

Good luck!

这篇关于数独生成算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！