Fork/Join Sudoku Solver

Question

I've a problem with an exercise. I need to find all the solutions for a given sudoku, using fork/join parallelism. I made an algorithm but it seems it doesn't work. It stops at some point and I can't figure it out why.

Here's the code:

private static int counter;
private Cella[][] sudoku;
private int i;
private int j;
private int theCounter = 0;

public SudokuMulti(Cella[][] sudoku) {
    this.sudoku = sudoku;
}

public SudokuMulti(Cella[][] sudoku, int i, int j) {
    this.sudoku = sudoku;
    this.i = i;
    this.j = j;
}

//DELETED

// Copy the sudoku matrix
private Cella[][] createCopy() {
    Cella[][] toReturn = new Cella[9][9];
    for (int i = 0; i < 9; i++) {
        System.arraycopy(sudoku[i], 0, toReturn[i], 0, 9);
    }
    return toReturn;
}

And the code for the object Cella:

public class Cella {

private int current;

public Cella() {
    current = 0;
}

public Cella(int current) {
    this.current = current;
}

//Getter and Setter

My idea is to give to each thread the faculty to solve its own sudoku, given the "legal values" of the candidate cell. I then collect all threads in an ArrayList and ask them to fork with the last for. Every thread should return an Integer (0 for no success, 1 for success) in order to count how many possible sudokus can be solved.

However, the algorithm only covers 1/3 of the sudoku: after a certain point, it stops filling the cells and it just returns without completing it.

Can someone suggest me where I'm doing mistake(s) ?

Answer 1

I've found a solution. Here is the error:

// Copy the sudoku matrix
private Cella[][] createCopy() {
    Cella[][] toReturn = new Cella[9][9];
    for (int i = 0; i < 9; i++) {
        // !!ERROR!!
        System.arraycopy(sudoku[i], 0, toReturn[i], 0, 9);
    }
    return toReturn;
}

When I copy the array I fill it with the Cella object reference and not with a new one, so it causes data races.

The correct way to copy the matrix is:

private Cella[][] createCopy() {
    Cella[][] toReturn = new Cella[9][9];
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            toReturn[i][j] = new Cella(sudoku[i][j].getCurrent());
        }
    }
    return toReturn;
}