listes Trier du plus court au plus long

Question

J'ai récemment repris Prolog et essaie de faire un programme pour trouver une solution pour le célèbre casse-tête Tour Chevalier [trouvé ici]

En utilisant l'algorithme Warnsdorff je suis en train pour trouver tous les mouvements possibles à partir d'un endroit spécifique sur l'échiquier et ensuite faire le mouvement qui a le moins de mouvements possible une fois qu'il est fait, puis répétez le processus, mais j'ai du mal à trouver ledit mouvement.

Voici mon code jusqu'à présent

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

Étant donné que le nombre de mouvements possibles n'est compté après les trouver tout alors ma liste ne sont pas triées comment je besoin d'être.

par exemple avec cette entrée

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

le résultat devrait être

NewX = 4, 
NewY = 7, 
Score = 5 

mais je reçois

NewX = 1, 
NewY = 4, 
Score = 3 

Si quelqu'un pouvait me aider à NewX et NewY avec le score minimum ce serait génial

Answer 1

Une bonne solution est de représenter tous les mouvements possibles comme pairesN-Spot où (par exemple):

• N est le nombre de mouvements qui sont encore possibles à partir Spot
• Spot est un endroit où nous pouvons déménager à.

Sur cette liste, vous pouvez utiliser keysort/2 pour trier la liste de telle sorte que le premier élément des paires sont en non décroissante ordre. Par exemple, le premier élément de cette liste sera le point le plus contraint en termes de mouvements ultérieurs.

Vous êtes déjà assez proche de la solution. Je vous suggère de se concentrer d'abord une évaluation d'un seul mouvement possible, en termes d'un prédicat comme spot_freedom(S, F) qui calcule, pour une place   S les degrés de liberté   F (en comptant le nombre de mouvements qui sont encore possibles à partir   S).

Ensuite, vous pouvez simplement faire:

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

et ont, dans la liste SFs keysorted des points candidats. Vous pouvez ensuite sélectionner (par exemple) le premier élément de cette liste, ou sur:

member(_-Target, SFs) 

pour essayer les places disponibles dans l'ordre croissant de la liberté sur retours en arrière.

Notez que vous aurez probablement besoin d'arguments supplémentaires pour spot_freedom, tels que l'historique des déplacements déjà effectués, pour détecter les points déjà occupés. Je pars comprendre cela comme un exercice.