F＃のバックトラッキングアルゴリズム：不変性はどのように機能しますか？

Question

[OK]を、ので、私は次のように入力を取ることができますバックトラッキングアルゴリズム記述しようとしています：

**c*** 
that** 
**toga 
***p** 

私がこれまで持っているコードは次のとおりです：

のように、

0 2 3 1 (top-right location, length, horizontal or vertical) 
1 0 4 0 
2 2 4 0 
1 3 3 1 
top (the actual words) 
that 
toga 
cat 

そして、クロスワードを吐き出すをここで

//prints the puzzle 
let printPuzzle (puzzle : char[,]) = 
    printfn "%s" "" 
    printfn "%A" puzzle 
    printfn "%s" "" 

//checks if the words fits 
let rec doesItFit place (puzzle : char[,]) (word : seq<char>) = 
    let (row, col, length, isVertical) = place 
    if length <> (Seq.length word) then 
     (puzzle, false) 
    else 
     match (Seq.toList word) with 
     | [] -> (puzzle, true) 
     | letter::rest -> 
      printfn "%c" letter 
      printPuzzle puzzle 
      if isVertical = 0 then 
       if puzzle.[row, col] = '*' || puzzle.[row, col] = letter then 
        puzzle.[row, col] <- letter 
        doesItFit (row, col+1, length-1, isVertical) puzzle rest 
       else 
        (puzzle, false) 
      else 
       if puzzle.[row, col] = '*' || puzzle.[row, col] = letter then 
        puzzle.[row, col] <- letter 
        doesItFit (row+1, col, length-1, isVertical) puzzle rest 
       else 
        (puzzle, false) 

//the actual backtracking algorithm... goes through all places and all words 
//trying to make stuff fit 
let rec sort words places (puzzle : char[,]) = 
    match places with 
    | [] -> (puzzle, true) 
    | place::rest -> 
     let rec checkWords words place puzzle = 
      match words with 
      | [] -> 
       printfn "%s" "failure, backtracking" 
       puzzle, false 
      | word::otherWords -> 
       let attempt = doesItFit place puzzle word 
       if snd attempt then 
        printfn "%s" "success, entering if block" 
        let nextLevel = sort words rest (fst attempt) 
        if (snd nextLevel) then 
         nextLevel 
        else 
         checkWords otherWords place puzzle 
       else 
        checkWords otherWords place puzzle 
     checkWords words place puzzle 

//line for testing 
printPuzzle (fst (sort ["cat"; "that"; "toga"; "top"] [(0, 2, 3, 1); (1, 0, 4, 0); (2, 2, 4, 0); (1, 3, 3, 1)] (Array2D.create 6 6 '*')));; 

テストラインを実行しているから出力されます：

c 

[['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

a 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

t 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['*'; '*'; 'a'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

success, entering if block 
t 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['*'; '*'; 'a'; '*'; '*'; '*'] 
['*'; '*'; 't'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

h 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; '*'; 'a'; '*'; '*'; '*'] 
['*'; '*'; 't'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

a 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; '*'; '*'; '*'] 
['*'; '*'; 't'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

t 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; '*'; '*'; '*'] 
['*'; '*'; 't'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

success, entering if block 
t 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

h 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

a 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

t 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; 'a'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

success, entering if block 
t 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; 'a'; 't'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

o 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; 'a'; 't'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

failure, backtracking 
t 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; 'a'; 't'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

o 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; 'a'; 't'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

failure, backtracking 
t 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; 'a'; 't'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

o 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; 'a'; 't'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

failure, backtracking 
t 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; 'a'; 't'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

failure, backtracking 

[['*'; '*'; 'c'; '*'; '*'; '*'] 
['t'; 'h'; 'a'; 't'; '*'; '*'] 
['*'; '*'; 't'; 'h'; 'a'; 't'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*'] 
['*'; '*'; '*'; '*'; '*'; '*']] 

私はだと思います。私の問題は、F＃で不変性がどのように機能するかわかりません。私のプログラムが、失敗した試行の後にパズルが渡されたときに、パズルが修正されたように見えます。 F＃で修正されないと思っていたので、それは私には分かりません。私が望むのは、元の修正されていないパズルではなく、このコードがバックトラック後に単語をテストするときにこのパズルが修正パズルを使用する理由の説明です。

Answer 1

あなたのコードは、パズルを表現するために可変配列char[,]を使用していますので、あなたは（<-演算子を使用して）doesItFit機能でそれを変異させたとき、あなたは実際にオブジェクトの状態を変更しています。コードがdoesItFit関数から戻ると、配列が変更されています。

は、問題を解決するために、基本的に3つの方法があります。パズルを表現する

• 利用不変タイプ - （あなたがパズルを表現するためのF＃のリスト（リストのリスト）を使用する場合は、あなたがそれを変異することはできませんが一覧表示されますので、このような状況にならないようにしてください。

• 必要に応じてオブジェクトを複製する - 機能的スタイルでコードを書くために不変型を使用する必要はありません。それを突然変異させる可能性のある関数に渡す前に配列をクローンするだけです。これにはArray.copyを使用できます。

• バックトラッキング前の状態を復元する - 関数が失敗したとき、それは（これは純粋に機能的なアプローチではありませんが、それは、より効率的であるかもしれない - 最適化と考える）すべての修正
  を元に戻す必要があります