java - 当其他线程中数据会发生变化时实现多线程

Question

我有一个单线程数独解算器，我想在其中使用多线程。我计划将 N 个线程委托(delegate)给板上的每个数组。每个线程将返回他们在正在处理的每个单元格中找到的可能性的数量，然后我们从那里测试这些值并在必要时回溯。

我所困扰的是，一旦线程在板上插入可能的值，如何保持所有内容同步，因为它改变了其他线程中可能性的数量。

我正在使用一种名为“最受约束的变量”的启发式方法。在每一步中，我们都会计算每个单元格中的可能性数量，并尝试在该单元格中找到一个具有最少可能候选值的值，以最大限度地减少冲突。例如:

 1 2  0 0
 0 0  0 0

 0 0  0 0
 0 0  3 4

第 1 行第 3 列的候选数最少 (1)，只能放 4 个。这是算法的核心，也是我想要使用多线程并行化的内容。

这是我用来解决数独难题的类:

public class LogicalSolver
{
    private int numberOfSteps;
    public LogicalSolver()
    {
        numberOfSteps = 0;
    }
    public boolean runLogicSolver(SudokuBoard board)
    {
        return logicalSolver(board);
    }
    private boolean logicalSolver(SudokuBoard board)
    {
        boolean solved = false;
        int row = -1;
        int column = -1;
        int candidates[] = new int[board.GRIDSIZE];
        int numOfCandidates = 0;
        for (int currentRow = 0; currentRow < board.GRIDSIZE; currentRow++)
        {
            for (int currentColumn = 0; currentColumn < board.GRIDSIZE; currentColumn++)
            {
                if (board.getValue(currentRow, currentColumn) == 0)
                {
                    int newCandidates[] = getCandidates(board, currentRow, currentColumn);
                    int numOfNewCandidates = getNumOfNewCandidates(newCandidates);
                    if (row < 0 || numOfNewCandidates < numOfCandidates)
                    {
                        row = currentRow;
                        column = currentColumn;
                        candidates = newCandidates;
                        numOfCandidates = numOfNewCandidates;
                    }
                }
            }
        }
        if (row < 0)
        {
            solved = true;
        }
        else
        {
            for (int i = 0; i < candidates.length && candidates[i] != 0; i++)
            {
                board.setValue(row, column, candidates[i]);
                numberOfSteps++;
                if (logicalSolver(board))
                {
                    solved = true;
                    break;
                }
                board.setValue(row, column, 0);
            }
        }
        return solved;
    }
    private int[] getCandidates(SudokuBoard board, int row, int column)
    {
        int newCandidates[] = new int[board.GRIDSIZE];
        int index = 0;
        for (int value = 1; value <= board.GRIDSIZE; value++)
        {
            boolean collision = false;
            for (int offset = 0; offset < board.GRIDSIZE; offset++)
            {
                int rowSubGrid = (row - row % board.ROWS) + (offset / board.ROWS);
                int columnSubGrid = (column - column % board.COLUMNS) + (offset % board.COLUMNS);
                if (board.getValue(row, offset) == value || board.getValue(offset, column) == value
                   || board.getValue(rowSubGrid, columnSubGrid) == value)
                {
                    collision = true;
                    break;
                }
            }
            if (!collision)
            {
                newCandidates[index] = value;
                index++;
            }
        }
        return newCandidates;
    }
    private int getNumOfNewCandidates(int newCandidates[])
    {
        int numOfNewCandidates = 0;
        for (int i = 0; i < newCandidates.length && newCandidates[i] != 0; i++)
        {
            numOfNewCandidates++;
        }
        return numOfNewCandidates;
    }
    public void displayNumberOfSteps()
    {
        System.out.println("It took " + numberOfSteps + " steps to solve this puzzle. \n");
    }
}

Answer 1

我认为这将是使用 ForkJoinTask 和 ForkJoinPool 的绝佳场所。

在解决方案的每一步中，您都会创建一个新的 ForkJoinTask 来探索每个可能的下一步。

每个任务都有自己正在研究的状态副本，因此在设置单元格时无需同步。相反，设置单元格会生成一个新的 ForkJoinTask 来探索设置该单元格的后果。

如果您必须同步，那么您就会失去多线程的一些好处。