Parallel Sudoku Solver in Java

Question

I have a homework that requires to implement a sequential and a parallel version of a sudoku solver in Java (using the ForkJoin Framework for the parallel one).

I wrote the sequential one and it works fine. The algorithmic idea is a simple backtracking exercise: for each cell (starting from the top-left corner of the table) not already filled, fill it (sequentially, and one at a time) with all the legal candidates (integer from 1 to 9) until you reach the end (row 9 col 9) of the matrix. If you've reached the end, then increments the solutions number.

I thought to implement the parallel version just spawning a new thread for each valid candidate found for a particular cell, and then waiting for them.. It seems not to work and I wasn't able to find the reason.

I post the class that should do the entire work with the hope to find a good advice:

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

First, you should consider what happens if one thread finishes it's job. You should note that it tries to reset the cell to 0, but what if there's another sub-thread working with the Cell?

Obviously, if another thread accessing the same Cell tries to check if it's legal, it may have to put a wrong value because another thread put a zero back in it!

Answer 2

I think you should pass the copy of the array to the new threads. In your code, you pass the same array to all the threads and they try to insert the correct value at the same time.