I make a copy of the array so that if a path turns out to be a failure (no solution can be found), I can unroll the stack and try a different path.

I think you are taking the wrong approach here. Take advantage of the mutability of the array and simply set the cell value to Unsolved again when a recursive call cannot find any solution. That way, you don't have to copy arrays all the time and fiddle with immutability. And it's obviously faster.

If you just want an immutable array for debugging purposes, you could use a simple wrapper:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

 

type ImmutableArray2D<'T>(data) =
   new(width, height, init:'T) = ImmutableArray2D<'T>(Array2D.create width height init)

   // (returns a new wrapped array)
   member this.Set(x,y,newval) =
      let data' = Array2D.copy data
      data'.[x,y] <- newval
      new ImmutableArray2D<'T>(data')

   // to support ".[x,y]" syntax

   member this.Item
      with get(x,y) = data.[x,y]


// some testing
let d = new ImmutableArray2D<_>(9,9,' ')
printfn "%c" d.[4,4]
let d' = d.Set(4,4,'A')
printfn "%c" d'.[4,4]

All this array copying after every change is very expensive, so for real code, this should not be used. More sophisticated immutable data structures use sharing of unchanged parts and are much more efficient.

Okay, so from what you have described, the data structure you are currently using does have an immutable interface. I suppose the main difference between what you have and a standard immutable data structure is that you are not reusing any of the unchanged data when you perform an immutable update.

There are more traditionally immutable data structures that provide the same interface as a 2d array. If you wanted to take a purely functional approach, you could use a purely functional quad tree--except, since the width of your matrix is not divisible by two, you would probably have to divide it into 9 pieces rather than 4. A more efficient option would be to use Chaung-style immutable array.

The thing is, I'm not sure how the above data structures would help you with your debugging process. Why do you think they would help you track down the source of your error? Because they only update data that changes rather than copying a bunch of redundant data? I don't think the approaches I described are going to be any more legible in this regard. Shouldn't the entire change history of a given 2d array be on the stack? What more debugging info do you need? The only thing I can think of that would help by this would be to pair each 2d array up with the change history that produced it--but, as I said, this info should already be on the stack.