How to use multithreading to solve sudoku-like puzzle in scala?

I'm wondering how to best use multithreading to solve a sort-of sudoku puzzle in Scala. What I start with is a 2D array, made into a 1D array for easier traversing. Every element in the array consists of a Square class, which holds all possible options for that square. I have already obtained the options by reducing from what already exists on the board.

What I do next is using recursion, moving from square to square in > direction from x(0, 0) to x(n, n). I try each option in each square, and if a square is out of options to try, it returns to a previous square that has more options.

This DOES work, but it goes really slow for puzzles over 10 x 10. I was thinking using multi threading might speed up the process? Am I somehow able to introduce multi threading into my current solution? If not, how could I best use multi threading to speed up the progress of solving the sudoku-like puzzle.

def next(Squares: Array[Square], step: Int): Unit = {

  val sq: _Square = SQs(i)

  for (o <- sq.options) { // check each o in square options
    val valid = isValidValue(SQs, sq, o) // scan row/column to check if option is valid
    if (valid) {
      sq.value = o // sets value of square to option
      next(Squares, step + 1) // use recursion to step into next square in squares
    }
  }
}

Here is an example of a 4x4 puzzle:

__ __ __<__
 A
__  1 __ __
 A
__ __>__ __

 1 __ __ __

and the solution

 2  4  1< 3
 A         
 3  1  4  2
 A         
 4  3> 2  1
           
 1  2  3  4