search

AlexP11223 / EightPuzzleSolver

8-puzzle solver. A*, RBFS, IDS algorithms, different puzzle sizes.
MIT License
12 stars 3 forks source link

Loops endlessly on 4x4 #1

Open Noemata opened 7 years ago

Noemata commented 7 years ago

The solver spins through 3x3, 4x3, and 3x4 boards to a solution nicely given any of the heuristic variations, but it spins endlessly on 4x4 boards. Was this tested?

I tried generating the board several times just in case the IsSolvable check was failing.

After playing around a little more, I did notice 4x4 puzzles being solved, but only after a 3x3 had been previously solved.

So to duplicate what I'm doing, immediately change to a 4x4 puzzle after launching the application, generate a new puzzle and try to solve. I could never get this working. Perhaps there is some initialization issue for the 4x4 code path?

AlexP11223 commented 7 years ago

Yeah, I mentioned in the readme that it doesn't work well for 4x4 and bigger. Probably needs better algorithm/heuristics. such as Disjoint Pattern Database.

I did notice 4x4 puzzles being solved, but only after a 3x3 had been previously solved.

Maybe it simply generated easier puzzle? If you were using random puzzles each time.

Noemata commented 7 years ago

Most of the published code on the net fails on a 4x4 puzzle. In fact, I've only found one solver that works every time, and very quickly. It uses a brute force algorithm and comes up with a sub optimal answer in under a second for a 4x4 puzzle. The smart approaches tend to get "lost" and never produce an answer. I've let your code spin for 3 hours on a relatively easy 4x4 puzzle on a very fast machine before stopping it.

I'm surprised that smart back tracking isn't talked about more often with respect to this problem. The other A* code I've looked at lacks the smarts to know when to stop searching. You're looping code is one such example. Adding a simple check for an iteration limit would make the code a little bit smarter. Had you weighted the search path, and then back tracked to the next best candidate after the iteration limit is hit, the search would be even smarter.

I've also seen minimal use of threading.

ZYLHL commented 3 years ago

I'd like to ask about how I can change the goal board to the state below. state

AlexP11223 commented 3 years ago

I'd like to ask about how I can change the goal board to the state below.

It's initialized here https://github.com/AlexP11223/EightPuzzleSolver/blob/57bc1d5c4a7f49cae074eef18b559426de225dfa/EightPuzzleSolverApp/Model/PuzzleSolverService.cs#L16, you can pass the goal as the second parameter.

PRs adding it in UI are welcome :)

Also please do not ask your questions in old unrelated issues like this one.