Блог

Главная - Вопросы по программированию - алгоритм открытия рыцарского тура (обратного отслеживания) в smlnj

алгоритм открытия рыцарского тура (обратного отслеживания) в smlnj

#algorithm #sml #backtracking #knights-tour

#алгоритм #sml #обратное отслеживание #рыцарский тур

Вопрос:

Я должен написать SML-код, чтобы решить проблему knight’s tour при обратном отслеживании. Шахматный конь должен пробежать по всей шахматной доске (размер: NxN ) и должен посетить каждую клетку ровно один раз (нет необходимости возвращаться на первую клетку в конце).

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

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

 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;
}

Комментарии:

1. Если вы знаете, как написать это на C, напишите / вставьте C, и мы поможем вам преобразовать его в SML.

2. Я отредактировал свой вопрос из-за ограничений веб-сайта… (Я не могу ответить на свой вопрос в течение 24 часов, и он был слишком большим для комментария)

3. что ж, это подходящее место для его выражения — вы не должны публиковать обновление своего вопроса в качестве ответа, а комментарии не могут содержать большие блоки кода.

4. ОК. Я только что отредактировал условие while сейчас… Я перевернул его.

5. Как вы думаете, у вас найдется время помочь мне?

Ответ №1:

Не думайте, как C! Это отвратительный способ мышления! Разработка вашего алгоритма на C / imperative никогда не помогает. Вам нужно сделать домашнее задание и научиться правильно мыслить.

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