如何使用Grand Central Dispatch并行化Sudoku求解器? [英] How to parallelize Sudoku solver using Grand Central Dispatch?

问题描述

作为编程练习，我刚完成编写使用回溯算法的Sudoku求解器(请参见

As a programming exercise, I just finished writing a Sudoku solver that uses the backtracking algorithm (see Wikipedia for a simple example written in C).

要更进一步，我想使用Snow Leopard的GCD对此进行并行化，以便它可以在我的计算机的所有内核上运行.有人可以给我指点我应该如何做以及应该进行哪些代码更改吗?谢谢！

To take this a step further, I would like to use Snow Leopard's GCD to parallelize this so that it runs on all of my machine's cores. Can someone give me pointers on how I should go about doing this and what code changes I should make? Thanks!

马特

推荐答案

例如，由于回溯是深度优先的搜索，因此它不能直接并行化，因为任何新计算的结果都不能被另一个线程直接使用.相反，您必须尽早划分问题，即线程#1从回溯图中的节点的第一个组合开始，然后继续搜索该子图的其余部分.线程#2从第一个的第二个可能的组合开始，依此类推.简而言之，对于 n 个线程，在搜索空间的顶级位置找到 n 个可能的组合(不要向前跟踪")，然后为这些 n个分配起点指向 n 个线程.

For one, since backtracking is a depth-first search it is not directly parallelizable, since any newly computed result cannot be used be directly used by another thread. Instead, you must divide the problem early, i.e. thread #1 starts with the first combination for a node in the backtracking graph, and proceeds to search the rest of that subgraph. Thread #2 starts with the second possible combination at the first and so forth. In short, for n threads find the n possible combinations on the top level of the search space (do not "forward-track"), then assign these n starting points to n threads.

但是我认为这个想法从根本上来说是有缺陷的:许多数独排列都是通过数千个正向+反向跟踪步骤解决的，并且在数毫秒内就可以在单个线程上解决.实际上，这是如此之快，以至于即使是几个线程所需的少量协调(假设 n 个线程将计算时间减少到原始时间的1/ n 个)，核心/多CPU与总运行时间相比不可忽略，因此绝不是一个更有效的解决方案.

However I think the idea is fundamentally flawed: Many sudoku permutations are solved in a matter of a couple thousands of forward+backtracking steps, and are solved within milliseconds on a single thread. This is in fact so fast that even the small coordination required for a few threads (assume that n threads reduce computation time to 1/n of original time) on a multi-core/multi-CPU is not negligible compared to the total running time, thus it is not by any chance a more efficient solution.

这篇关于如何使用Grand Central Dispatch并行化Sudoku求解器?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！