数独在C ++中的求解 [英] Sudoku solving in c++

问题描述

我最近一直在使用c ++进行数独游戏.我已经使用SFML制作了它的图形版本，并且效果很好.但是，我需要实现一种可以解决数独功能的算法，而不是是一种蛮力算法(因此，回溯对我不起作用;/).我已经读过许多解决它的方法，并且遇到了不同的算法名称(例如Dancing Links)，以及仅描述搜索工作原理的算法，而没有提供有关如何实现搜索的任何特定信息. C ++. (即为每个存储桶"分配一个表或可能的数字列表，并寻找解决方案，有人还提到了所谓的A *算法吗?)

I've recently been working on a sudoku game in c++. I've made a graphic version of it using SFML and it works just fine. However, I need to implement an algorithm which will solve the sudoku, whilst not being a brute-force algorithm (so backtracking doesn't work for me ;/). I've read about many ways to solve it and I've come across different algorithm names (such as Dancing Links), as well as algorithms which only describe how the search works without giving any specific pieces of information on how to implement it in c++. (i.e. assigning a table or a list of possible numbers to each single "bucket" and searching for the solution, also someone mentioned so-called A* algorithm?)

所以这是我的问题，哪种算法比较容易实现，不是回溯算法?在哪里可以找到有关如何在c ++中使用它的特定信息?提前致谢. 我的程序在二维数组上运行，但是如果需要，我可以通过某种方式将存储桶变成结构.

So here is my question, what kind of algorithm is fairly easy to implement and is not the backtracking one? And where to find specific pieces of information on how to use it in c++? Thanks in advance. My program works on a two-dimensional array, but I could somehow make the buckets into structures if needed.

推荐答案

Peter Norvig建议使用消除(约束传播)过程，然后进行搜索.他的文章此处提供了非常详尽的解释.

Peter Norvig recommends using process of elimination (constraint propagation) followed by search. His article here provides a very thorough explanation.

在约束传播中，您使用以下策略:

In constraint propagation you use the following strategy:

(1) If a square has only one possible value, then eliminate that value from the square's peers. 
(2) If a unit has only one possible place for a value, then put the value there.

现在，您很容易在 O(N)时间内找到拼图中最初填充的正方形.将它们全部放入队列.如果他们的邻居在传播约束后只有一个值，请将其添加到队列中.重复直到队列为空.

Now, it's easy to find in O(N) time the initially-filled squares in the puzzle. Put them all in a queue. If their neighbours, after propagating the constraint, have only a single value, add that to the queue. Repeat until the queue is empty.

这个难题现在已经解决，或者通过传播约束条件无法取得进一步的进展.

The puzzle is now either solved or no further progress can be made by propagating constraints.

如果未解决难题，则可以使用更高级的算法，也可以按照Norvig的建议使用回溯.由于回溯是在拼图空间的一小部分子集上执行的，因此您无需使用蛮力.

If the puzzle is not solved, you could either use a fancier algorithm or, as Norvig recommends, employ backtracking. Since the backtracking is being performed on a typically-small subset of the puzzle space, you're not using brute-force.

这篇关于数独在C ++中的求解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！