algorithm - smlnj中开放骑士之旅(回溯)算法

Question

我必须编写 SML 代码来解决回溯中的骑士旅行问题。国际象棋骑士必须跑遍棋盘(大小:NxN)并且必须恰好访问每个方格一次(不需要最后回到第一个方格)。

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

您将如何设计程序？它要存储状态，每个状态都要记录骑士去了哪里。将您的状态设计为棋盘元组(遍历的 bool 记录方 block 列表)和移动((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)