用多线程并行执行解决网格大小大于9*9的数独问题
用多线程并行执行解决网格大小大于9*9的数独问题
提问于 2017-04-24 12:12:17
我正在做一个项目，我要解决一个数独难题N^2*N^2，其中N小于20。
我已经编写了一个单线程数独解程序，它可以很好地处理N值为5的谜题，但是如果我增加N的值，比如N=10或20，代码就会变得没有响应。我还尝试使用线程池(java.concurrent)并分配线程的N^2数来并行执行。但这是行不通的，谁也不能给我任何解决方案，这可以提高性能。
下面是我的单线程方法：
public class SUDOKU {
public static int[][] grid;
public boolean solveSUDOKU() {
int row;
int col;
int[] blankCell = findBlankLocation();
row = blankCell[0];
col = blankCell[1];
if (row == -1) {
// means will have filled the grid, return;
return true;
}
// we need to fill grid[row][col] cell
for (int i = 1; i <= grid.length; i++) {
// check if number i is safe for grid[row][col] cell
if (isSafe(row, col, i)) {
// means its safe to fill the number
grid[row][col] = i;
// fill the rest of the grid
if (solveSUDOKU()) {
return true;
}
// if we are here that means current selection of number didnt
// work, revert back the changes
grid[row][col] = 0;
}
}
return false; // This will cause the backtracking
}
public boolean isSafe(int row, int col, int n) {
// we need to check row contains number n OR
// Column contains number n OR
// Block in which cell appears contains number n
// If Any of the above statement is true, return false
if (!UsedInRow(row, n)
&& !UsedInColumn(col, n)
&& !UsedInBox((int) (row - row % Math.sqrt(grid.length)),
(int) (col - col % Math.sqrt(grid.length)), n)) {
return true;
}
return false;
}
// check if n not in particular row
public boolean UsedInRow(int row, int n) {
for (int i = 0; i < grid.length; i++) {
if (grid[row][i] == n) {
return true;
}
}
return false;
}
// check if n not in particular column
public boolean UsedInColumn(int col, int n) {
for (int i = 0; i < grid.length; i++) {
if (grid[i][col] == n) {
return true;
}
}
return false;
}
// check if n not in particular box
public boolean UsedInBox(int boxStartRow, int boxStartCol, int n) {
for (int i = 0; i < Math.sqrt(grid.length); i++) {
for (int j = 0; j < Math.sqrt(grid.length); j++) {
if (grid[i + boxStartRow][j + boxStartCol] == n) {
return true;
}
}
}
return false;
}
public int[] findBlankLocation() {
int[] cell = new int[2]; // cell[0]-row cell[1] -column
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid.length; j++) {
if (grid[i][j] == 0) {
cell[0] = i;
cell[1] = j;
return cell;
}
}
}
cell[0] = -1;
cell[1] = -1;
return cell; // means grid is full
}
public void print() {
for (int row = 0; row < grid.length; row++) {
if (row % Math.sqrt(grid.length) == 0) {
System.out.println(); // for more readability
}
for (int col = 0; col < grid.length; col++) {
if (col % Math.sqrt(grid.length) == 0) {
System.out.print(" "); // for more readability
}
System.out.print(grid[row][col] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
grid = new int[][]{
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
SUDOKU s = new SUDOKU();
if (s.solveSUDOKU()) {
s.print();
} else {
System.out.println("NO SOLUTION");
}
}
}回答 1
Stack Overflow用户
回答已采纳
发布于 2017-04-24 13:00:06
事情没那么简单。您不会在问题上抛出“并行”和“更多线程”，这样就可以神奇地提高性能。
在您的例子中，您需要覆盖一个巨大的搜索树。含义:您的方法可能被称为数百万次。
因此，首先要做的事情是：理解您的代码正在做什么。
意思:你可以从简单的打印语句开始，或者添加“调用计数器”。或者，如果查找现有的分析工具，这些工具可以帮助您理解中的哪些部件，您的程序花费了大部分时间。然后你开始研究优化的方法。
第一个，很明显的候选人:你在计算
Math.sqrt(grid.length)就像在3到5个不同的地方。这是一个相当昂贵的解决方案。sqrt()可以很容易地避免(通过计算值一次并将其放入所有其他代码将使用的常量)。它也可能是值得研究的模块计算(尽管这种计算可能更难摆脱)。
除此之外，为了使并行化您的代码，您必须了解该代码是如何处理其数据的。您知道，不能只使用n个线程来处理相同的单个数字数组。因为突然之间，您必须担心consistency；，您不能让一个线程覆盖内容，而另一个线程正在读取它。
因此，最基本的答案是：
- 理解单线程场景中的代码。
- 优化您的单线程解决方案，避免任何太昂贵的问题。
然后，当您真正了解您的代码正在做什么时，您仍然不高兴；然后您可能会考虑在您的问题上抛出“更多的线程”。但即使如此:请记住，线程并不是免费的。在它们之间创建和切换有很大的开销。对于纯粹的CPU密集型操作来说，拥有更多的线程不会有多大帮助。
当有大量IO操作(以及等待从IO读取数据的线程)时，线程有助于提高吞吐量。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/43587779
复制相关文章
相似问题
腾讯云开发者
