Сортировка списков от коротких до самой длинной

Question

Я недавно взял пролог, и я пытаюсь сделать программу, чтобы найти решение для знаменитой головоломки Тур Рыцарский [здесь]

Используя алгоритм Warnsdorff я пытаюсь чтобы найти все возможные шаги, которые могут быть сделаны из определенного места на шахматной доске, а затем сделать ход, который имеет наименьшие возможные шаги после его создания, а затем повторить этот процесс, однако мне трудно найти указанный ход.

Вот мой код до сих пор

possibleKnightMove(I, J, I1, J1) :- I1 is I+1, J1 is J+2. 
possibleKnightMove(I, J, I1, J1) :- I1 is I+2, J1 is J+1. 
possibleKnightMove(I, J, I1, J1) :- I1 is I+2, J1 is J-1. 
possibleKnightMove(I, J, I1, J1) :- I1 is I+1, J1 is J-2. 
possibleKnightMove(I, J, I1, J1) :- I1 is I-1, J1 is J-2. 
possibleKnightMove(I, J, I1, J1) :- I1 is I-2, J1 is J+1. 
possibleKnightMove(I, J, I1, J1) :- I1 is I-2, J1 is J-1. 
possibleKnightMove(I, J, I1, J1) :- I1 is I-1, J1 is J+2. 

possible_knight_moves(Rows, Columns, X, Y, Visited, NewX, NewY) :- 
    possibleKnightMove(X, Y, NewX, NewY), 
    NewX > 0, NewX =< Rows, 
    NewY > 0, NewY =< Columns, 
    \+ member([NewX,NewY], Visited). 

possible_moves_count(Rows, Columns, X, Y, Visited, Count) :- 
    findall(_, possible_knight_moves(Rows, Columns, X, Y, Visited, _NewX, _NewY), Moves), 
    length(Moves, Count). 

warnsdorff(Rows, Columns, X, Y, Visited, NewX, NewY, Score) :- 
    possible_knight_moves(Rows, Columns, X, Y, Visited, NewX, NewY), 
    possible_moves_count(Rows, Columns, NewX, NewY, [[NewX, NewY] | Visited], Score). 

Поскольку число возможных ходов считается только после того, как найти их все, то мой список не отсортирован, как мне нужно, чтобы это было.

, например, с этим входом

warnsdorff(8,8,3,5,[[1,1],[2,3],[3,5]], NewX, NewY, Score). 

результат должен быть

NewX = 4, 
NewY = 7, 
Score = 5 

однако я получаю

NewX = 1, 
NewY = 4, 
Score = 3 

Если кто-то может помочь мне получить NewX и NewY с минимальным счетом это было бы здорово

Answer 1

Хорошим решением будет представлять все возможные ходы, как парN-Spot где (например):

• N является количество ходов, которые все еще можно дальше от Spot
• Spot это место, мы можем перейдите к.

В таком списке, вы можете использовать keysort/2 для сортировки списка таким образом, что первый элемент пары в неубывающей заказа. Например, первый элемент этого списка будет местом, которое наиболее ограничено с точки зрения дальнейших ходов.

Вы уже достаточно близко к решению. Я предлагаю вам первый сфокусировать оценку один возможный ход, в терминах предиката типа spot_freedom(S, F), который вычисляет, на месте   S степеней свободы   F (подсчет количества ходов, которые еще возможно от   S).

Затем, вы можете просто сделать:

findall(F-S, spot_freedom(S, F), SFs0), 
keysort(SFs0, SFs) 

и есть, в SFs в keysorted список кандидатов пятен. Затем можно выбрать (например) первый элемент этого списка, или использовать:

member(_-Target, SFs) 

попробовать доступные места в порядке возрастания свободы на возвраты.

Обратите внимание, что вам, вероятно, понадобятся дополнительные аргументы для spot_freedom, такие как история уже сделанных шагов, чтобы определить, какие пятна уже заняты. Я оставляю это как упражнение.