smlnj中开启骑士之旅（回溯）算法

Question

我必须编写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;
}

Answer 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)