Backtracking doesn't require a mutable anything, per se. Just the ability to get back to where you were.
Now, it can be somewhat easily reasoned that a mutable board can more quickly let you go back to previous settings, since you could potentially lose the GC steps of the immutable version.
Of course, the immutable is more easily reasoned for parallelizing, since you can just throw paths to different workers without them stepping on each other.
So, tradeoffs.