Параллельный Судоку Солвер на Яве

Question

У меня есть домашнее задание, которое требует реализации последовательной и параллельной версии решателя судоку в 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'

Answer 1

Во-первых, вы должны рассмотреть, что произойдет, если один поток завершит свою работу. Вы должны заметить, что он пытается сбросить ячейку до 0, но что, если есть другой подпоток, работающий с ячейкой?

Очевидно, что если другой поток, обращающийся к той же ячейке, попытается проверить, допустимо ли это, ему, возможно, придется ввести неправильное значение, потому что другой поток вернет ноль обратно в него!

Answer 2

Я думаю, что вы должны передать копию массива новым потокам. В своем коде вы передаете один и тот же массив всем потокам, и они одновременно пытаются вставить правильное значение.