2

我必须编写 SML 代码来解决回溯中的骑士之旅问题。象棋骑士必须跑遍整个棋盘（大小：NxN），并且必须在每个方格中准确访问一次（最后不需要回到第一个方格）。

我已经编写了所有函数来创建一个空棋盘，设置或获取棋盘中的方块，获取可能的骑士下一步动作列表。但是我不知道如何在 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/命令式中制定你的算法永远不会有帮助。你需要做功课并学会正确思考。

你将如何设计程序？它必须存储状态，并且每个状态都必须记录骑士去了哪里。将您的状态设计为棋盘元组（遍历的布尔记录方块列表）和移动（（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 回答