정렬 목록 짧은에서 가장 긴에

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 및 NewY를 얻을 수 있도록 할 수 있다면

NewX = 4, 
NewY = 7, 
Score = 5 

그러나 나는

NewX = 1, 
NewY = 4, 
Score = 3 

를 얻을 수 있어야한다 그게 좋을거야

,

Answer 1

좋은 해결책은 (예를 들어) 쌍N-Spot 모든 가능한 움직임을 표현하는 것이다

• N가 Spot
• Spot에서 여전히 가능 움직임 수인 곳 우리가 할 수있다 로 이동하십시오. 이러한 목록에서

, 당신은 순서를 비 감소 쌍의 첫 번째 요소는 에 있도록 목록을 정렬 할 keysort/2를 사용할 수 있습니다. 예를 들어,이 목록의 첫 번째 요소는 추가 이동의 관점에서 가장 제한된 지점이됩니다.

당신은 이미 해결책에 가깝습니다. 난 당신이 먼저이 자리, 계산 spot_freedom(S, F) 같은 조건의 관점에서, (  S에서 여전히 가능 움직임의 수를 계산) 자유   F의   S 정도를 하나의 가능한 움직임을 평가 초점을 제안한다. SFs에 후보 지점의 keysorted 목록을

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

을하고 있습니다

그렇다면, 당신은 간단하게 할 수 있습니다. 그런 다음 (예를 들어)이 목록의 첫 번째 요소를 선택하거나 사용할 수 있습니다

member(_-Target, SFs) 

가 역 추적에 자유의 순서를 증가에서 사용할 수있는 지점을 시도 할 수 있습니다.

spot_freedom에 대한 추가 인수 (예 : 이미 수행 한 이동 기록)가 이미 사용 된 스팟을 감지 할 수 있습니다. 나는 이것을 운동으로 생각하고있다.