0

私は最近プロローグを手に入れ、有名なパズル Knight's Tour [ここにあります] の解決策を見つけるプログラムを作成しようとしています。

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それは素晴らしいことです

4

1 に答える 1

0

良い解決策は、すべての可能な動きをペア N-Spotとして表すことです (例):

  • Nからまだ可能な移動の数です。Spot
  • Spot移動できる場所です。

このようなリストでは、 を使用keysort/2して、ペアの最初の要素が減少しない順序になるようにリストを並べ替えることができます。たとえば、このリストの最初の要素は、それ以上の移動に関して最も制限されている場所になります。

あなたはすでに解決にかなり近づいています。最初に、自由度 ( からまだ可能な移動の数を数えます )spot_freedom(S, F)を計算する ような述語の観点から、単一の可能な移動を評価することに焦点を当てることをお勧めします。SFS

次に、次のように簡単に実行できます。

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

そして、SFs候補スポットのキーソートされたリストにあります。次に、(たとえば) このリストの最初の要素を選択するか、次を使用できます。

member(_-Target, SFs)

バックトラックの自由度の高い順に利用可能なスポットを試す。

spot_freedomどのスポットがすでに占有されているかを検出するために、すでに行われた移動の履歴など、 の追加の引数が必要になる可能性が高いことに注意してください。演習としてこれを理解することはやめておきます。

于 2016-06-10T09:17:23.457 に答える