Распараллелить реализацию алгоритма возврата

Question

Я хочу распараллелить реализацию алгоритма возврата, который выглядит следующим образом

public class SudokuBoard
{
    public bool Solve()
    {
        if(!IsValid)
            return false;

        BasicSolveAttempt();
        if(IsSolved)
            return true;

        SudokuCell targetCell = SelectUndeterminedCell();
        foreach(var possibleSolution in targetCell.PossibleSolutions)
        {
            SudokuBoard attemptBoard = new SudokuBoard(this);
            attemptBoard.SetCell(targetCell, possibleSolution);
            if(attemptBoard.Solve() == true)
            {
                this.Copy(attemptBoard);
                return true;
            }
        }  
    }
}

В моей первой попытке я использовал Task.Factory.StartNew() для каждого possibleSolution а потом Task.WhenAny() останавливаться и проверять при каждом возвращении задачи, как следует

public Task ParallelSolve()
{
    if(!IsValid)
        return false;

    BasicSolveAttempt();
    if(IsSolved)
        return true;

    SudokuCell targetCell = SelectUndeterminedCell();

    var tokenSource = new CancellationTokenSource();
    List<Task<SudokuBoard>> attemptTasks = new List<Task<SudokuBoard>>();

    foreach(var possibleSolution in targetCell.PossibleSolutions)
    {
        SudokuBoard attemptBoard = new SudokuBoard(this);
        attemptBoard.SetCell(targetCell, possibleSolution);

        var token = tokenSource.Token;
        speculationTasks.Add(
            Task.Factory.StartNew(() =>
                {
                    attemptBoard.ParallelSolve().Wait(token);
                    return attemptBoard;
                },
                token)
        );
    }

    while (attemptTasks.Count > 0)
    {
        Task<SudokuBoard> completedTask = await Task.WhenAny(attemptTasks);
        SudokuBoard attemptBoard = completedTask.Result;
        if (attemptBoard.IsValid() && attemptBoard.IsSolved())
        {
            tokenSource.Cancel();
            this.CopyBoard(attemptBoard);
            return;
        }
        attemptTasks.Remove(completedTask);
    }
}

тем не мение

• Накладные расходы от создания потоков кажутся слишком большими
• Я не уверен, что все еще выполняющиеся задачи правильно останавливаются, когда решение найдено