> The fact that Board is immutable means we don't have to perform any cleanup when backtracking. What does it mean? When one of the branches is stuck in a dead end, we must slowly go back, trying to take all other possible moves. Mutating Board would require cleaning it up. Immutable Board can be simply thrown away once it's no longer needed. Also immutability enables concurrent exploration (soon to come).
Someone correct me if I'm wrong, but I believe backtracking actually requires a mutable array and would be faster (since you wouldn't have to build 100x100 arrays all the time: you could just build the 100x100 array one time and mutate it.)