2

バックトラッキングでのナイトツアーの問題を解決するには、SML コードを作成する必要があります。チェス ナイトはチェス盤 (サイズ: ) のいたるところを走らなければNxNならず、各マスを 1 回だけ訪れなければなりません (最後に最初のマスに戻る必要はありません)。

空のボードを作成する関数、ボード内の正方形を設定または取得する関数、騎士の次の動きのリストを取得する関数はすべて既に作成しています。しかし、再帰関数を SML で記述する方法がわかりません (このアルゴリズムを C で記述する方法は知っていますが、SML では記述できません)。

8x8 チェス盤の C のアルゴリズム

dl and dr are array : (delta to calculate next moves)   
dl = [-2,-2, -1, 1, 2,  2, 1, -1]  
dr = [-1, 1,  2, 2, 1, -1,-2, -2]

bool backtracking(int** board, int k /*current step*/, int line, int row, int* dl, int* dr) {
    bool success = false;
    int way = 0;

    do {
        way++;
        int new_line = line + dl[way];
        int new_row = row + dr[way];

        if (legal_move(board, new_line, new_row)) {
            setBoard(board,new_line, new_row,k); //write the current step number k in board
            if (k < 64) {
                success = backtracking(board, k+1, new_line, new_row, dl, dc);
                if (!success) {
                    setBoard(board,new_line, new_row,0);
                }   
            }
            else
                success = true;
        }
    } while(!(success || way = 8));

    return success;
}
4

1 に答える 1

1

Cのように考えるな！考え方がおかしい！C/命令でアルゴリズムを実行しても、決して役に立ちません。宿題をして、適切に考える方法を学ぶ必要があります。

プログラムをどのように設計しますか？状態を保存する必要があり、各状態は騎士がどこに行ったかを記録する必要があります。ボードのタプル (通過した bool 記録正方形のリストのリスト) と移動 ((int, int) のリスト) のタプルになるように状態を設計します。したがって、関数呼び出しは次のようになります。

exception Back
fun iter (state, []) = 
      if boardFull state then state else raise Back
  | iter (state, next::ns) =
      iter (next, states next) handle Back => iter (state, ns)

fun states (board, ps) =
    <a move is a pair (int, int); write out the list of eight moves; map a next fn down the list, and filter it by legal moves> (2 or 3 lines of code for you to write)
fun boardFull (board, pos::ps) = <foldl twice to apply the 'and' fn over the whole board> (1 line of code for you to write)
于 2011-05-08T21:13:19.023 に答える