Алгоритм открытого рыцарского тура (backtracking) в smlnj

Question

Мне нужно написать код SML, чтобы решить проблему с рыцарским туром в обратном направлении.Шахматный рыцарь должен бегать по всей шахматной доске (размер: NxN) и должен посещать каждый квадрат ровно один раз (нет необходимости возвращаться в первый квадрат в конце).

Я уже записал все функции длясоздайте пустую доску, чтобы установить или получить квадраты на доске, чтобы получить список возможных ходов коня.Но я понятия не имею, как написать рекурсивную функцию в SML (я знаю, как написать этот алгоритм на C, но не на SML).

Алгоритм на C для шахматной доски 8x8

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 / Imperative никогда не помогает. Вам нужно делать домашнее задание и учиться правильно мыслить.

Как вы будете разрабатывать программу? Он должен хранить состояние, и каждое государство должно записывать, куда ушел рыцарь. Сделайте так, чтобы ваше состояние было кортежом доски (список списков пройденных булевых квадратов) и ходов (список (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)