問題タブ [sliding-tile-puzzle]

そこで、8 タイル パズルの空白のタイルがスライドする方向を見つけようとしています。

X/Y を使用してタイルを決定しています。

これが私が持っているコードです。

私が得ている問題は、マンディスト述語を呼び出すときに、期待した結果が得られないことです。

問題はifステートメントにあると確信しています。私がやろうとしていることを理解できるように、いくつかの疑似コードを書きました。

例：

次に、mandist 述語を呼び出します

D が 1 に設定されているため、合法的な動きが保証されます。

予想外の結果は次のとおりです。

Direction = rightまた、位置 1/1 は 3x3 グリッドの左下であり、左下からの移動は上または右のいずれかのみであるため、それが言うことも期待しています。

1/3 2/3 3/3

1/2 2/2 3/2

1/1 2/1 3/1

I'm trying to implement a solver of an 8-puzzle. The puzzle board is represented as a list. For example, the goal state:

is represented as [1,2,3,4,5,6,7,8,0], where 0 represents the empty space.

I've implemented move(+Board,-Move) that succeeds with Move as all the possible states of the board one move away from Board. In addition I've implemented solvable(+Board) that gives true or false as to whether the board can be solved.

I've also implemented two heuristics, manhattan(+Board,+Goal,-H) and hamming(+Board,+Goal,-H), which calculates the heuristics cost from Board to Goal. For example:

I want to implment solve(+Board,+Heuristic,-Solution) that succeeds with Solution as one optimal solution to Board using the Heuristic given, and it must terminate deterministically with precisely one solution. For example:

I wrote out the pseudo code for the A* algorithm:

Where G(Board) is the actual cost of Board, defined as the length of the optimal path to Board from the initial board. F(Board) is the combined cost of Board, defined as the sum of G(Board) and the estimated cost of Board (defined by a heuristic function). And of course Closed and Open are the two sets maintained by the A* algorithm, with Closed containing boards that have been visited, Open containing boards that have not.

Issue is I have no idea how to do this in Prolog. I suppose that some heap datastructure is necessary to maintain the two list, but have no idea what or how. Any help would be great.

8 パズル ゲームの dfs 検索を実装しましたが、何らかの理由で正常に機能させることができません。スタックは 8 パズル ゲームの可能な動きを追加し続けますが、答えが減ることはありません。それが正常かどうかはわかりませんが、誰かが私を助けることができる場合に備えて、ここに私のコードがあります。

コードが完全に最適化されていないことはわかっています。dfs が機能しない理由を知りたいだけです。ありがとうございます。