2

我有一个作业需要在 Java 中实现数独求解器的顺序和并行版本（使用 ForkJoin 框架进行并行）。

我写了顺序的，它工作正常。算法思想是一个简单的回溯练习：对于每个尚未填充的单元格（从表格的左上角开始），用所有合法候选者（从 1 到 9 的整数）填充（按顺序，一次一个） ) 直到到达矩阵的末尾（第 9 行第 9 行）。如果您已到达终点，则增加解决方案编号。

我想实现并行版本，只是为为特定单元格找到的每个有效候选者生成一个新线程，然后等待它们。它似乎不起作用，我无法找到原因。

我发布了应该完成整个工作的课程，希望能找到一个好的建议：

class SolveSudoku extends RecursiveAction{
    private int i, j;
    private int[][] cells;

    SolveSudoku(int i, int j, int[][] cells){
        this.i = i;
        this.j = j;
        this.cells = cells;
    }

    @Override
    protected  void compute(){
        if (j == 9) {
            j = 0;
            if (++i == 9){
                solutions++;
                System.out.println(solutions);
                return;
            }
        }

        if (cells[i][j] != 0 ){                             // skip filled cells
            SolveSudoku s =  new SolveSudoku(i, j+1, cells);
            s.compute();
            return;
        }


        ArrayList<Integer> vals = new ArrayList<Integer>();
        for (int val = 1; val <= 9; val++)                 // try all the legal candidates for i, j
            if (legal(i,j,val,cells))
                vals.add(val);


        if(vals.size() == 1){                            // only one, no new threads
            cells[i][j] = vals.get(0);
            new SolveSudoku(i, j+1, cells).compute();
        }
        else{
            SolveSudoku threads[] = new SolveSudoku[vals.size()];
            int n = 0;
            int first;
            for(int k=0; k<vals.size(); k++){
                if(k == vals.size()-1){
                    cells[i][j] = vals.get(k);
                    threads[n] = new SolveSudoku(i, j+1, cells);
                    threads[n].compute();
                }
                else{
                    cells[i][j] = vals.get(k);
                    threads[n] = new SolveSudoku(i, j+1, cells);
                    threads[n].fork();
                }
                n++;
            }


            for(int k=0; k<threads.length-1; k++)
                if(k != vals.size()-1)
                    threads[k].join();

        }

        cells[i][j] = 0;
        return;
    }}

new ForkJoinPool().invoke(new SolveSudoku(0, 0, M)); // where *M* is a sudoku instance to solve where all the unfilled cells contain '0'
4

2 回答 2

0

首先，您应该考虑如果一个线程完成它的工作会发生什么。您应该注意到它试图将单元格重置为 0，但是如果有另一个子线程在使用该单元格怎么办？

显然，如果另一个线程访问同一个 Cell 尝试检查它是否合法，它可能必须输入错误的值，因为另一个线程将零放回其中！

于 2016-12-26T16:26:43.610 回答
0

我认为您应该将数组的副本传递给新线程。在您的代码中，您将相同的数组传递给所有线程，并且它们尝试同时插入正确的值。

于 2016-12-30T02:30:22.670 回答