search

jgardner8 / NPuzzle

N-Puzzle solved with several tree-based search algorithms.
6 stars 1 forks source link

Incorrect Solution #1

Open Nazalas opened 6 years ago

Nazalas commented 6 years ago

I believe that there may be something wrong with the AS solver. The puzzle below gives me a solution which runs out of bound of the puzzle.

4x4 1 4 8 10 5 9 11 2 0 14 3 7 6 13 15 12 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0

Broken into a 4x4, it should look like this 1 4 8 10 5 9 11 2 0 14 3 7 3 13 15 12

but the solution provided doesn't seem to fit. Down;Right;Right;Down;Down;Left;Left;Up;Right;Up;Left;Down;Right;Right;Down;Right;Up;Up;Left;Down;Right;Down;Left;Left;Left;Up;Right;Up;Right;Up;Right;Down;

jgardner8 commented 6 years ago

Thanks for bringing this to my attention, I was able to reproduce it. In fact, it looks like the problem is bigger than just A*.

I tried the 2x2.txt puzzle and it gave an out of bounds result for that too. This program definitely worked before. It's either a user problem (we're misinterpreting what exactly those actions mean or how the puzzle files expand into a 2d puzzle) or possibly a Python update changing the behaviour of the program.

I don't have time to work on this anymore unfortunately. If you come up with a solution let me know.

Nazalas commented 6 years ago

I will if I get some time. Do you happen to have any articles or documentation on the methods you use to solve this kind of problems? I understand the search algorithms themselves but not really in respect of this particular issue.

On Thu, May 10, 2018, 7:15 PM James Gardner notifications@github.com wrote:

Thanks for bringing this to my attention, I was able to reproduce it. In fact, it looks like the problem is bigger than just A*.

I tried the 2x2.txt puzzle and it gave an out of bounds result for that too. This program definitely worked before. It's either a user problem (we're misinterpreting what exactly those actions mean or how the puzzle files expand into a 2d puzzle) or possibly a Python update changing the behaviour of the program.

I don't have time to work on this anymore unfortunately. If you come up with a solution let me know.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/jgardner8/NPuzzle/issues/1#issuecomment-388213408, or mute the thread https://github.com/notifications/unsubscribe-auth/AExm-9L4sVj6JVZcMCKFZSa1hmiBMkjsks5txMoagaJpZM4T6F3Y .

jgardner8 commented 6 years ago

I'm afraid not. Basically it's a search from the initial state to the desired state. A* has a heuristic that tries to determine how close a given state is to the desired state, so the search is informed and doesn't just go off in every direction. While there's no high level documentation, the code commenting is fairly comprehensive, so if you have a vague understanding of how this works then trawling through the code may help.

If you're interested in AI in general this project is better documented: https://github.com/jgardner8/genetic-tetris-ai